报告人:侯建鹏
报告日期：2012/4/16
1004 Max Sum Plus Plus
解题思路：
动态规划的思想。
1.基本思路：
首先，定义数组p[n],a[m][n].
p[n]用来存储n个整数组成的序列.
a[i][j]用来表示由前j项得到的含i个字段的最大值，且最后一个字段以p[j]项结尾。仔细想想，我们可以知道： a[i][j]=max(a[i][j-1]+p[j],a(i-1,t)+p[j]) 其中i-1<=t<=j-1.
所求的最后结果为 max( a[m][j] ) 其中1<=j<=n.
但是，我们会发现，当n非常大时，这个算法的时间复杂度和空间复杂度是非常高的,时间复杂度近似为O(m*n^2),空间复杂度近似为O(m*n).因此，我们需要优化算法来降低时间复杂度和空间复杂度.
2.优化算法：
(1)节省时间
由基本思路，我们可以知道，a[i][j]=max(a[i][j-1]+p[j],a(i-1,t)+p[j])，其中i-1<=t<=j-1.我们只要找到a[i][j-1]和a[i-1][t]的最大值加上p[j]即为a[i][j].所以，定义一个数组pre_max[n]，用pre_max[j-1]来表示求解a[i][j]时a[i][j-1]的最大值,则a[i][j]=max(pre_max[j-1],a[i][j-1])+p[j].
特别注意，pre_max[n]这个位置的存储空间是始终用不到的，因此可以用来存储其他数值，在接下来会用到。 在求解a[i][j]的同时，我们可以计算出a[i][t];i<=t<=j的最大值，这个最大值在计算a[i+1][j+1]的时候需要作为pre_max[j]的形式被使用，我们先把它存在pre_max[n]中。
你可能会问：问什么不把它直接放在pre_max[j]中呢？因为你接下来需要计算a[i][j+1]的值，需要用到pre_max[j]中原来的值，如果你把它存在这里，就会覆盖掉计算a[i][j+1]所需要的那个值。所以，先把它放在pre_max[n]中。 当我们计算完a[i][j+1]之后，就会发现pre_max[j]中的值已经没有用处了，我们可以把它更新为计算a[i+1][j+1]所需要的那个值，即之前放在pre_max[n]中的那个值，即执行pre_max[j]=pre_max[n].
这样我们就节省了计算最大值时付出的时间代价。
(2)节省空间
通过时间的节省，我们突然间发现程序执行结束后pre_max[n]的值即为最后的结果，pre_max[n]数组才是我们希望求解的，a[m][n]这个庞大的数组已经不是那么重要了，因此，我们现在用整型数a来代替a[m][n]，用来临时存储a[i][j]的值，作为求解pre_max[n]的中介。
这样就节省了a[i][j]占用的极大的空间.
#include<stdio.h> #include<string.h> #define N 1000010 int p[N],pre_max[N]; int max(int a, int b) { return a>b?a:b; } int main() { //freopen("input.txt","r",stdin); int m , n , i , j , a , b ; while(scanf("%d%d",&m,&n)==2) { for(i=1;i<=n;i++) scanf("%d",&p[i]); memset(pre_max,0,sizeof(int)*N); for(i=1;i<=m;i++) { a=0; for(b=1;b<=i;b++) a+=p[b]; pre_max[n]=a; for(j=i+1;j<=n;j++) { a=max(pre_max[j-1],a)+p[j]; pre_max[j-1]=pre_max[n]; pre_max[n]=max(pre_max[n],a); } } printf("%d\n",pre_max[n]); } return 0; }