如何使用分治法解決「固定大小的最大子陣列」？

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