分割と征服のアプローチを使用して "固定サイズの最大サブアレイ"を解決するには？

Question

免責事項：私はこの問題が非常に効率的に配列の単一パスで解決できることを知っていますが、分裂と征服に取り組む典型的な問題とは少し異なるので、分割と征服でこれを行うことに興味があります。

サイズnと間隔長lの浮動小数点配列X [1：n]が与えられたとします。問題は、最大総和を持つ配列から長さlのサブ配列を見つけるために分割および征服アルゴリズムを設計することです。

これは私が思いついたものです。長さnの配列には、l個の連続する要素のn-l + 1個のサブ配列があります。たとえば、長さn = 10およびl = 3の配列の場合、長さ3の8つのサブ配列が存在します。

ここで問題を2つの半分に分割するために、n-l + 1/2となるので、下のアルゴリズムに示すように、同じ数のサブアレイが私の分割の両側に分配されます。再び、n = 10、l = 3、n-l + 1 = 8のため、（n-1 + 1）/ 2 = 4で問題を分割しましたが、4番目のサブアレイでは、 6すなわち（n + 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

分裂と征服は必要ありません。単純な1パスアルゴリズムをタスクに使用することができます。その配列は十分に大きいとしましょう。その後、オリジナル最大サブアレイ問題は、実際にD＆C（これは、任意の所与の間隔についてだけでなく、その間隔における最大サブアレイも左端から始まる最大サブアレイを計算することを含むことによってうまく解決することができるが

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