問題の説明：n要素を含む配列、これらのn要素は正または負になる可能性があります。最大のサブアレイの合計を見つけます。
方法1：ブルートフォースメソッド
アイデア：考えられる最も簡単で簡単な方法は、すべてのサブアレイを見つけて、すべてのサブアレイの合計を見つけ、すべてのサブアレイの合計で最大値を取得することです。
/ ***方法1（ブルートフォースメソッド）：2つのループで最大サブアレイの合計を見つけます*/ public static int maxsubarray1（int [] a）{int i、j; int thissum = 0; int maxsum = 0; for（i = 0; i <a.length; i ++）{thissum = a [i]; for（j = i+1; j <a.length; j ++）{thissum+= a [j]; if（thissum> maxsum）{maxsum = thissum; }} maxsumを返します。 }方法2：最適化された動的プログラミング
アイデア：最初に、アレイの最後の要素A [n-1]と最大のサブアレイの関係によれば、次の3つの状況に分けることができます。
1）最大サブアレイには、[n-1]、つまり[n-1]で終わることが含まれています。
2）[n-1]のみが最大のサブアレイを形成します。
3）最大サブアレイには[n-1]が含まれていないため、[1、...、n-1]の最大サブアレイを見つけることは、[1、...、n-2]の最大サブアレイを見つけるために変換できます。
上記の分析を通じて、次の結論を導き出すことができます。最大のアレイ（[0]、... a [i-1]）の合計がすべて[i-1]として計算されており、[i-1]の[i-1]の最大配列の合計は、end [i-1]としても計算されます。
次に、次の関係を取得できます。すべて[i-1] = max {a [i-1]、end [i-1]、すべて[i-1]}。この式と動的プログラミングのアイデアを使用して、問題を解決します。 （コードは、位置を開始し、終了位置を開始する問題も解決します）
/ ***方法2：最適化された動的プログラミング方法* nendは、順番に[i]に配列を追加し、[i]と比較することによって取得され、より大きなものを保存しました。 static int max（int m、int n）{return m> n？m：n; nend = nend+a [i]; maxsum = integer.min_value; int nstart = 0; for（int i = 0; i <a.length; i ++）{if（nsum <0）{nsum = a [i]; nstart = i; } else {nsum+= a [i]; } if（nsum> maxsum）{maxsum = nsum; begin = nstart; end = i; }} maxsumを返します。 }上記はこの記事のすべての内容です。この記事の内容が、すべての人の勉強や仕事に役立つことを願っています。また、wulin.comをもっとサポートしたいと思っています！