0

この問題への入力は、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. アルゴリズムが実際に線形時間で実行される理由を簡単に説明してください。
4

1 に答える 1

0

アイテムを取らない場合 (したがって、解は空の部分配列になります)、0解としてあります。そのため、ルールは次のとおりです。

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

少しトリッキーな瞬間は、合計中に負の数に遭遇することです。

 3, 4, 5, -1 ...

そのままにしておく (そして を持っている3 + 4 + 5 == 12) か、正の数がすぐに現れることを期待して受け取ることができます。

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

sumこのあいまいさを解決するには、a までの最良のものを記憶し、result合計し続けることができます。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 }));
于 2016-12-12T07:51:14.863 に答える