Реализовать простой алгоритм с использованием divide и conquer

Question

Я пытаюсь реализовать следующий алгоритм, используя метод divide и conquer, чтобы получить время выполнения O (n * logn).

Учитывая последовательность чисел a_1, a_2, ..., a_N и числа к, находим I и J, такие, что 1 < = J - я < = к, максимизируя a_i + a_j.

Например, для последовательности 10,2,0,8,1,7,1,0,11 и к = 2, максимальное значение равно 15 = 8 + 7.

Я выполнил какой-то метод разделения и завоевания, но я изо всех сил пытаюсь понять, как проверять значения, которые проходят через каждый из интервалов разделения. Вот то, что я до сих пор:

int MaxInterval(int array[], int left, int right, int k) 
{ 
    int BestSum = 0; 
    int sumL = 0; 
    int sum = 0; 
    int sumR = 0; 
    int sumMid = 0; 
    int count = 0; 
    if(right - left <= 2*k-3) // 
    { 
     //elaborate straightforward search right way 
     for(int i = left; i <= right; i++) 
     { 
      sum = 0; 
      count = k; 
      for(int j = i+1; j <= right; j++) 
      { 
       if(count == 0) break; 
       sum = array[i] + array [j]; 
       if(sum > BestSum) BestSum = sum; 
       count--; 
      } 

     } 
     return BestSum; 
    } 
    int mid = (right + left)/2; 
    sumL = MaxInterval(array, left, mid, k); 
    sumR = MaxInterval(array, mid + 1, right, k); 
    sumMid = MaxInterval(array, max(left, mid - k + 2), min(right, mid + k - 1), k); 
    return max(max(sumL, sumR), sumMid); 
} 

Я думаю, что я на какой-то-то, что на правильном пути, я просто изо всех сил, чтобы выяснить, как включить контрольные суммы чисел, которые идут по двум интервалам , без использования метода грубой силы, который бы дал сложность O (n^2).

Если есть какие-либо указатели или советы о том, как я могу продолжить это, мы будем признательны. Кроме того, я в настоящее время работаю в предположении, что в массиве существует четное число целых чисел. Спасибо, парни.

Answer 1

Некоторые ключи в псевдокоде. Пример для n = 8, k = 2 - этот код будет искать лучший результат из [0..3], a [4..7] и [2..5]. Обратите внимание, что я удалил дополнительные массивы.

int MaxInterval(int array[], int left, int right, int k) 
{ 
    if(right - left <= 2*k-1) // 
    { 
     //elaborate straightforward search right way 
     return BestSum; 
    } 
    sumL = MaxInterval(array, left, mid, k); 
    sumR = MaxInterval(array, mid + 1, right, k); 
    sumMid = MaxInterval(array, max(left, mid - k + 1), min(right, mid + k), k); 
    return max(sumL, sumR, sumMid); 
}