まず最初に、このサイトでいくつかの解決策を見てきましたが、私はダイナミックなプログラミング方法でそれをしたいので、私の質問にマッチしない。n個の整数の配列をM個の連続したサブシーケンスに分割して、パーティションの最大値が最小になるようにします。
私はすべてを試しましたが、本当に失われました。整数の連続をM連続サブシーケンスに分割して、パーティションの最大値が最大になるようにする必要があります。
例：{4,8,7,10,40,15,30,2,1,20}およびM = 4 アルゴリズムは{4,8,7,10} {40} { 15,30} {2,1,20}です。今では最大合計が15 + 30 = 45です。このサイトでは動作しなかった投稿を見ました。すべての助けてくれてありがとう！
Aまっすぐ動的プログラミングソリューション：
iは、現在のパーティションの最後の要素であり、jは、部品の数がパーティションにしていた状態が、(i, j)あります。
状態の値はこれまでの最大合計です。
トランジションはmax(f(i, j), sum(i + 1, k)) -> f(k, j + 1)です（これは[i + 1, k]部分を取ることを意味します）。
答えはです（これは、Nの要素をとり、正確にMのグループを作成したことを意味します）。
シーケンス全体を取り、いずれかの側に1つの要素のパーティションを切り捨てることによって最大合計パーティションを見つけることができます。カットオフ要素の合計が最小限になるように、これを実行する必要があります。
これは、1つの整数の自由度（最初から切り取る要素の数）を与えます。したがって、0からM - 1までこの番号を繰り返すことができます（最後から切り取る要素の数は明らかにM - 1 - iです）。 、これはつながるあなたの例では
に：
{4}, {8}, {7}, {10, 40, 15, 30, 2, 1, 20}
任意のパーティションの最大合計が、その後118
であるが、負の数はありますか？ –
正の数のみ –