如何用分治法解决“固定大小最大子数组”？

Question

免责声明：我知道这个问题可以通过数组的单次传递非常有效地解决，但我对用分而治之法做这个很感兴趣，因为它与我们用分而治之法处理的典型问题有点不同。

假设给定一个浮点数组x[1:n]，大小为n，间隔长度为l。问题是设计一个分治算法，从具有最大和的数组中找到长度为l的子数组。

现在，为了将问题分成两半，我决定在n-l+1/2处中断数组，以便将相等数量的子数组分配到我的除法的两半，如下面的算法所示。同样，对于n=10，l=3，n-l+1=8，所以我把问题分解为(n-l+1)/2=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

我的关注：为了应用分而治之，我在两个数组中都使用了一些数据元素，所以我正在寻找另一种避免额外存储的方法。

Answer 1

你不需要分而治之。一个简单的一次通过算法可以用于该任务。让我们假设，这个数组足够大。然后：

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;
    }
}