1.定義

給定由n個整數（可能為負）組成的序列a1、a2、a3...,an, 以及一個正整數m，要求確定序列的

如給定一個數組{1，-2，3，4，-5，-6}和一個正整數m=2，明顯當兩個子段分別為{1}和{3，4}時，得到最大m子段和，最大m子段和為8。

2.思路

可以利用動態規劃的思想解決該問題。

定義二維數組dp，令dp[i][j]表示前 j 項所構成 i 子段的最大和，且必須包含著第j項，即以第j項結尾。(這個定義很重要，一定要理解)。

舉個例子，如dp[3][4]則表示以a4結尾，並且和a4前面的項所構成的3子段和的最大值。簡單來說，就是a0a1a2a3a4中分成3段，包含a4且以a4結尾，這3子段和是最大的。（例如可能是a0、a1、a4這三段）

所以，dp[i][j]總共有兩種可能。

1.若a[j]和a[j-1]合成一段，此時 dp[i][j] = dp[i-1][j] + a[j]

2.a[j]單獨成段，然後往a[j]前面的項找i-1個子段最大和，此時dp[i][j] = dp[i-1][t]+a[j](i-1≤t

最後取這兩種情況中的最大值，賦給dp[i][j]。

3.例子

根據思路，實戰一把，例如有一個數組

arr={1，-2，3，4，-5，-6}，可以根據以上思路做出下表。例如我們要求圖中的星星部分的值，也就是

dp[2][4]的值，首先第一種情況是a[4]與前面的a[3]連成一段，即該種情況下的dp[2][4]的值為dp[2][3]+a[4]=8+(-5) = 3；第二種情況是，a[4]自成一段，並且看看其之前的項中，i-1段最大和為多少，可以看到為7，所以該種情況下的dp[2][4]的值為dp[1][3]+a[4] = 7 + (-5) = -2；取第一種情況與第二種情況中的最大值，為3，填入dp[2][4]中。

我們可以從上往下，從左往右把整張表填完。

那麼，假如要求m=2時的最大子段和為多少時，可以看到第2行中，dp[2][3]的時候最大，為8。

另外找i-1子段的最大和，可以使用滾動輔助數組來完成，不用重新遍歷。即，再上一輪填空的過程中，記錄j列之前（包括j列）的最大值，以供此輪填表使用。

4.參考代碼

閱讀更多 IT界的泥石流 的文章

關鍵字: 最大 最大值 a1