0

実行時間を O(n*logn) にするために、分割統治法を使用して次のアルゴリズムを実装しようとしています。

一連の数値 a_1、a_2、…、a_n および数値 k が与えられた場合、a_i + a_j を最大化しながら 1<= j – i <= k となるような i と j を見つけます。

たとえば、シーケンス 10,2,0,8,1,7,1,0,11 および k = 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) 複雑さ。

これをどのように継続できるかについての指針やヒントがあれば、それは大歓迎です. また、私は現在、配列に偶数個の整数があるという仮定の下で作業しています。みんなありがとう。

4

1 に答える 1

1

疑似コードのいくつかの手がかり。n=8、k = 2 の例 - このコードは、a[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);
}
于 2012-05-21T04:59:45.057 に答える