0

我正在尝试使用分治法实现以下算法，以使运行时间达到 O(n*logn)。

给定一个数字序列 a_1、a_2、...、a_n 和一个数字 k，找到 i 和 j 使得 1<= j – i <= k，同时最大化 a_i + a_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 回答