题目链接：
题目描述：
给出n个数，问m段连续子序列的和相加最大是多少？
解题思路：
dp[i][j]表示把前i个元素(包括第i个)，分成j段的最大和。状态转移方程就是dp[i][j] = max (dp[i-1][j] + arr[j], max( dp[k][j-1]) + arr[j])，其中0<k<i。(第i个元素是保存在第j段，还是自己单独成段)
由于1<=n<=1000,000。n*n的数组肯定会爆炸，所以要对方程进行降维。观察可得，我们可以在状态转移的时候保存max(dp[k][j-1]),然后第一维就可以省去了。
1 #include <map> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 8 typedef int LL; 9 const LL maxn = 1000005; 10 const LL INF = 0x3f3f3f3f; 11 LL arr[maxn], cur[maxn], pre[maxn]; 12 13 int main () 14 { 15 LL n, m; 16 while (scanf ("%d %d", &m, &n) != EOF) 17 { 18 19 for (int i=1; i<=n; i++) 20 scanf ("%d", &arr[i]); 21 22 memset (cur, 0, sizeof(cur)); 23 memset (pre, 0, sizeof(pre)); 24 25 LL Max_sum; 26 27 for (int i=1; i<=m; i++) 28 { 29 Max_sum = - INF; 30 31 for (int j=i; j<=n; j++) 32 { 33 cur[j] = max(cur[j-1], pre[j-1]) + arr[j]; 34 pre[j-1] = Max_sum; 35 Max_sum = max(Max_sum, cur[j]); 36 } 37 38 } 39 40 printf ("%d\n", Max_sum); 41 } 42 return 0; 43 }
Hdu 1024 Max Sum Plus Plus (dp)
原文：http://www.cnblogs.com/alihenaixiao/p/4902516.html