最大多段子串和問題是一個杭電ACM的OJ題，是一個很典型的動態規劃問題。
網上關于這個問題有很多帖子都給出了相應的問題解決方法并附有代碼，但是我一開始看的時候非常費解，閑下來仔細琢磨了一下這個問題，這里將給出一個我對這個問題的理解。
首先我們看看這個問題的描述：
給定一個整數數組A[]；
給定數組元素個數N；
給定整數M；
求A[]中任意M個不相交的子串的最大和。
例如，給定A[] = {3, -2, 1, 4 ,-2, 5}， M = 2， N = 6，
那么，它擁有最大和的兩（M）個子串為{3}，{1， 4， -2， 5}，最大和為3 + 8 = 11
這個問題如何解決呢？
一開始就提到過這是個典型的動態規劃問題，動態規劃問題最核心的步驟就是找狀態轉移方程。
首先我給出一個比較直觀的解決方案，如下：
首先我們定義:
1.
maxsum[i][j]為前j個元素中i段和的最大值，也就是目標函數，最后我們要求的也就是max[M][N]
2. end_maxsum[i][j]為前j個元素中以第j個元素結尾的i段和的最大值
那么我們可以得到如下狀態轉移方程：
end_maxsum[i][j] = MAX(end_maxsum[i][j - 1] + A[j], maxsum[i - 1][j - 1] + A[j]); ----------------- 1
maxsum[i][j] = MAX(end_maxsum[i][j], maxsum[i][j - 1]); ----------------- 2
首先我們看第一個方程，end_maxsum[i][j]代表以第j個元素結尾的i段和的最大值，那么有兩種情況：
Case 1:
將A[j]直接接在第j-1個元素后面，并入前一個段，那么之前的分段必須以A[j-1]結尾，故為end_maxsum[i][j - 1]，{A[k],...}{...,A[j-1]} + A[j] -> {A[k],...}{...,A[j - 1], A[j]}， 作這種拼接不會增加段數i，此種情況下最大為end_maxsum[i][j - 1] + A[j]；
Case 2:
讓A[j]獨立作為一段，那么此時最大為maxsum[i - 1][j - 1] + A[j]；
將二者取一個最大的即可得到end_maxsum[i][j]。
得到了end_maxsum[i][j]之后，我們如何得到maxsum[i][j]呢？
首先end_maxsum[i][j]肯定是maxsum[i][j]的一個候選，它代表將A[j]拉入該多段子串的最大和；
還有什么情況呢？
那么就是丟棄A[j]的最大和，丟棄A[j]意味著maxsum[i][j] = maxsum[i][j - 1]；
所以我們只需要取MAX(end_maxsum[i][j], maxsum[i][j - 1])就可以得到maxsum[i][j]了。
自此，我們已經將動態規劃思路理清，現在我們就可以構造一個自底向上的解了（一般來說動態規劃都可以理解為自底向上地根據轉移方程填表），下面給出一個C++的簡單實現。
輸入格式為：
M N A[1] A[2] ... A[N]
輸出為最大和。
1 #include <iostream>
2
3 #define MAX 1000
4 #define MIN -1000
5
6 using namespace std;
7
8 int a[MAX];
9 int maxsum[MAX][MAX];
10 int end_maxsum[MAX][MAX];
11
12
13 int Max(int i, int j)
14 {
15 return i > j ? i : j;
16 }
17
18 int getTotalSum(int n)
19 {
20 int sum = 0;
21 for(int i = 1; i <= n; i++)
22 {
23 sum += a[i];
24 }
25 return sum;
26 }
27
28 int getMax(int m, int n)
29 {
30 if(n == m)
31 return getTotalSum(n);
32
33 for(int i = 1; i <= m; i++)
34 {
35 maxsum[i][i] = getTotalSum (i);
36 end_maxsum[i][i] = getTotalSum (i);
37 }
38
39 for(int i = 1; i <= m; i++)
40 {
41 int tempMax = getTotalSum (i);
42 for(int j = i + 1; j <= n; j++)
43 {
44 end_maxsum[i][j] = Max(end_maxsum[i][j - 1] + a[j], maxsum[i - 1][j - 1] + a[j]);
45 tempMax = Max(end_maxsum[i][j], maxsum[i][j - 1]);
46 maxsum[i][j] = tempMax;
47
48 //cout<<"dp["<<i<<"]["<<j<<"] "<<dp[i][j]<<endl;
49 }
50 }
51 return maxsum[m][n];
52 }
53
54 int main()
55 {
56 int n, m;
57 int result;
58 while(cin>>m>>n && (m > 0 || n > 0))
59 {
60 a[0] = 0;
61 for(int i = 0; i < n; i++)
62 {
63 cin>>a[i + 1];
64 }
65
66 result = getMax(m, n);
67 cout<<result<<endl;
68 }
69
70 return 0;
71 }這里需要說明一下，為了讓這個實現和之前描述的解題思路一致，這里采用了二維數組來記錄maxsum和end_maxsum，記錄了很多沒有用的信息，空間耗費較大，所以無法通過OJ。
實際上是可以用一維數組來記錄這些信息的，這樣可以大大減少空間，對應的實現在很多帖子上已經出現，大家可以去參考，思路和上面描述的差不多，但是實現上更加節省空間。
希望能對大家理解這個問題有所幫助。
歡迎各位大牛批評指正。
01/07/2014