hdoj Max Sum Plus Plus（DP）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024

题意：----最大M子段和问题
给定由 n个整数（可能为负整数）组成的序列a1，a2，a3，……，an，以及一个正整数 m，要求确定序列 a1，a2，a3，……，an的 m个不相交子段，
使这m个子段的总和达到最大，求出最大和。

思路：DP

用a数组表用示数据，dp[i][j]表示将前j个数划分成i个子段的和的最大值（a[j]包含在最后一个段中）。

则有状态转移方程：dp[i][j]=max(dp[i][j-1]+a[j] , dp[i-1][t]+a[j])，其中i-1<=t<=j-1。即将a[j]合并到最后一个段还是独立组成一个段。

这样的时间复杂度为O(m*n^2)，空间复杂度为O(m*n)，均比较大。

优化：在计算dp [i][j]时会花费大量时间计算dp[i-1][t] (i-1<=t<=j-1)，如果进一步用dp的思想将dp[i-1][t]的值在之前的计算中存储起来，那么时间复杂度将只有O(m*n)，那么可以用f[j-1]表示dp[i-1][t] (i-1<=t<=j-1)，于是发现f[n] 我们始终用不上。在计算dp[i][j] 时需要f[j-1]（此时的f[j-1]是i-1层的），在计算dp[i][j]的过程可以得到f[j]（i层的），但不能马上赋给f[j]，因为此时的f[j]存储的将前j个数据划分成i-1段的最大值，在计算dp[i][j+1]时需要，所以可以暂时存储在f[n]中，在计算完

dp[i][j+1]后之后再赋给f[j]。这样就省去了每次循环时计算dp[i-1][t]的时间。

同时我们会发现dp数组可以不需要了，可以用tmp临时表示dp[i][j]。这样就不需要dp这个耗空间巨大的数组了。

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=1e6+5;
 5 int n,m;
 6 int a[maxn],f[maxn];
 7 
 8 int dp(){
 9     int tmp;
10     for(int i=1;i<=m;i++){
11         tmp=0;
12         for(int j=1;j<=i;j++)
13             tmp+=a[j];
14         f[n]=tmp;
15         for(int j=i+1;j<=n;j++){
16             tmp=max(tmp,f[j-1])+a[j];
17             f[j-1]=f[n];
18             f[n]=max(f[j-1],tmp);
19         }
20     }
21     return f[n];
22 }
23 
24 int main(){
25     while(scanf("%d%d",&m,&n)!=EOF){
26         for(int i=1;i<=n;i++)
27             scanf("%d",&a[i]),f[i]=0;
28         printf("%d\n",dp());
29     }
30     return 0;
31 }

参考：https://www.cnblogs.com/dongsheng/archive/2013/05/28/3104629.html

hdoj Max Sum Plus Plus（DP）

原文：https://www.cnblogs.com/FrankChen831X/p/10372274.html