最大値隣接サブシーケンスアルゴリズム

Question

この問題への入力は、配列A[1...n]の実数です。隣接するサブシーケンスA[i],A[i+1],...A[j]のすべての数字を合計すると、最大値が何であるかを調べる必要があります。Aです。 Aに負の数が含まれていない場合、問題は簡単で、Aのすべての要素を合計することで解決できます。しかし、Aに正の数と負の数が混在していると、より難しくなります。

たとえば、A = [-2,11,-4,13,-5,-3]の場合、溶液は20（11-4 + 13 = 20）です。 A = [-2,1,-3,4,-1,2,1,-5,4]については、溶液は6（4-1 + 2 + 1 = 6）である。空のサブシーケンスの数の合計は0です。 はO（n^3）でこの問題を解決する強引なソリューションが存在する

、線形時間で問題を解決することも可能です。

1. 上記の問題を線形時間で解くアルゴリズムを設計します。あなたのアルゴリズムを擬似コードで表現する。
2. アルゴリズムがどのように、なぜあなたのアルゴリズムが機能するかを簡単に説明します。
3. アルゴリズムが実際に線形時間で動作する理由を簡単に説明してください。

Answer 1

我々は（そのソリューションは空の部分配列である）任意の項目をとらない場合、我々は解決策として0を持っています。

When running `sum` drops to `0` or below, restart summing. 

合算我々は負の数に実行しながら、少しトリッキーな瞬間がある：私たちはどちらかそれ（と3 + 4 + 5 == 12を持っている）、またはテイクを残すことができ

3, 4, 5, -1 ... 

ルールがある理由です それは、正の数はすぐに に表示されることを望ん：

3, 4, 5, -1, 100, 200, 300 

この曖昧さを解消するには、今までsumを最大まで記憶しておき、合計を続けます。 C＃実装：

private static double Solution(IEnumerable<double> source) { 
    // We can guarantee 0 (for empty subarray) 
    double result = 0; 
    double sum = 0; 

    // Linear: all we have to do is to scan the collection 
    foreach (var item in source) 
    if (sum + item <= 0) // when sum drops to zero 
     sum = 0;   // ... restart summing 
    else { 
     sum += item; 

     if (sum > result) // update the best sum so far on each decision 
     result = sum; 
    } 

    return result; 
} 

テスト：

// 6 
Console.WriteLine(Solution(new double[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 })); 
// 20 
Console.WriteLine(Solution(new double[] { -2, 11, -4, 13, -5, -3 }));