サブシーケンスは、溶液が透明でない

Question

は最大の合計と数字のシーケンスを見つけたプログラムを、書きます。 例：{2、3、-6、-1、2、-1、6、4、-8,8}

第2の方法は、アレイを1つのループで左から右へスキャンする方法です要素を合計します。 我々は負の合計を取得したら、我々は 次の要素から合計する再起動することができます。なぜこれが正しいのか考えてみてください！各ステップで、現在の合計が現在の最大値よりも大きいかどうかを確認します。

それは、このソリューションが動作する方法を...私は、私はこのソリューションを理解していないことを離れて歩くことができない別の方法で問題を解決したが、私にははっきりしていない...あなたはそれを説明してもらえますか？事前に助けていただきありがとうございます。

編集：私はありません、私は理解していないもので、別の方法でタスクを解決:)

Answer 1

をあなたが述べたように、あなたは一つのループに配列を反復し、合計Sを蓄積します。各ステップでS += a[i]を実行し、Sを現在の最大値max = Math.max(S, a[i])と比較します。我々はSときS < 0をゼロにすべき理由

あなたの質問はあります。これがステップiで発生したとします。 (S + a[i+1]) < a[i+1]（S < 0なので）。a[i+1]、つまりS = 0から新しいサブシーケンスを開始する方が最大の後続合計を探しているためです。