Блог

Отказ от ответственности:Я знаю, что эта проблема может быть решена с помощью одного прохода массива очень эффективно, но я заинтересован в том, чтобы сделать это с помощью «разделяй и властвуй», потому что это немного отличается от типичных проблем, которые мы решаем с помощью «разделяй и властвуй».

Предположим, вам предоставлен массив с плавающей запятой X [1: n] размером n и длиной интервала l. Проблема заключается в разработке алгоритма «разделяй и властвуй» для нахождения подмассива длины l из массива с максимальной суммой.

Вот что я придумал.Для массива длиной n существует n-l 1 подмассивы из l последовательных элементов. Например, для массива длиной n = 10 и l = 3 будет 8 подмассивов длиной 3.

Теперь, чтобы разделить проблему на две половины, я решил разбить массив на n-l 1/2, чтобы равное количество подмассивов было распределено на обе половины моего деления, как показано в алгоритме ниже. Опять же, для n = 10, l = 3, n-l 1 = 8, поэтому я разделил проблему на (n-l 1) / 2 = 4. Но для 4-го подмассива мне нужны элементы массива до 6, т.Е. (n l-1) /2.

 void FixedLengthMS(input: X[1:n], l, output: k, max_sum)
{
   if(l==n){//only one sub-array
      sum = Sumof(X[1:n]);
      k=1;
   }
   int kl, kr;
   float sum_l, sum_r;
   FixedLengthMS(X[1:(n l-1)/2], l, kl, sum_l);
   FixedLengthMS(X[(n-l 3)/2:n], l, kr, sum_r);

   if(sum_l >= sum_r){
      sum = sum_l;
      k = kl;
   }
   else{
      sum = sum_r;
      k = n-l 1/2   kr;
   }
}
  

Примечание: чтобы очистить индексацию массива
для подмассива, начинающегося с (n-l 1) / 2, нам нужны элементы массива до (n-l 1) / 2 l-1 = (n l-1) / 2

Моя проблема: для применения «разделяй и властвуй» я использовал некоторые элементы данных в обоих массивах, поэтому я ищу другой метод, который позволяет избежать дополнительного хранилища.

Более быстрый метод будет оценен по достоинству.

Пожалуйста, игнорируйте синтаксис раздела кода, я просто пытаюсь дать обзор алгоритма.

Вам не нужно разделять и властвовать. Для этой задачи можно использовать простой однопроходный алгоритм. Предположим, что массив достаточно большой. Затем:

 double sum = 0;
for (size_t i = 0; i < l;   i)
    sum  = X[i];

size_t max_index = 0;
double max_sum = sum;

for (int i = 0; i < n - l;   i) {
    sum  = X[i   l] - X[i];
    if (sum > max_sum) {
        max_sum = sum;
        max_index = i;
    }
}