나누기 및 정복을 사용하여 간단한 알고리즘 구현

Question

실행 시간을 O (n * logn)으로 만들기 위해 나누기 및 정복 방법을 사용하여 다음 알고리즘을 구현하려고합니다.

는 i와 j를 찾아되도록 1 < = J를 참조 A_1, A_2, ... a_n 및 번호 (k)의 시퀀스를 감안 - I < = K A_I + a_j을 극대화. 시퀀스 102081710,11 및 K = 2의 예

는 최대 값 = 8 + 7

I가 구현 15 어떤 종류의 나누기와 정복 방법이지만, 각 나누기 간격을 가로 지르는 값을 확인하는 방법을 알아 내려고 애 쓰고 있습니다.

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) 복잡도를 산출 할 수있는 brute-force 방법을 사용하지 않아도된다.

나는 이것을 계속할 수있는 방법에 대한 조언이나 조언이 있으면 크게 환영 할 것입니다. 또한, 배열에 짝수 개의 정수가 있다는 가정하에 현재 작업 중입니다. 고마워.

Answer 1

의사 코드의 몇 가지 단서. n = 8, k = 2의 예 -이 코드는 [0..3], a [4..7] 및 a [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); 
}