如何使用分治法解决“固定大小的最大子阵列”？

Question

声明：我知道这个问题可以非常有效地通过数组的一次传递来解决，但是我有兴趣用分而治之来做这件事，因为它与我们用分而治之解决的典型问题有点不同。

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

这是我想出来的。对于长度为n的数组，有l个连续元素的n-1 + 1个子数组。例如，对于长度为n = 10和l = 3的数组，将会有8个长度为3的子阵列。/2，以便相同数量的子阵列将分配给我的部门的两半，如下面的算法所示。再次，对于n = 10，l = 3，n-1 + 1 = 8，所以我在（n-1 + 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 + 1 - 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; 
    } 
}