动态规划小结（1）最大子段和

 1.对于一维问题，求解一个序列中的连续子段的最大和。状态：一维数组dp[i]：以i结尾的最大子段和，并非前i项的最大子段和，二者有区别。转移：if dp[i]>0         dp[i+1]=dp[i]+a[i]      else        dp[i+1]=dp[i]       ans=max(dp[k];k=1,2,....n),空间上可以用滚动数组的原理优化，空间复杂度O(1)。      if ans>0 dp+=a[i]      else dp=a[i]      ans=max(dp)hoj 1760 The jackpot2.二维。预处理出每行（列）的和，sum[i][j]表示第i行第1->j列的和。用O(n^3)的复杂度枚举所有的矩形，枚举一个行，两个列。对于一个矩形，行都缩为一个点，对列转化成为一维问题处理。hoj 2558 maxsum3.三维和二维转化成一维的情况完全类似。先预处理出底面（或其他面）的二维矩阵和。Sum[i][j][k]:第i层，对角端点为(1,1)和(j,k)的矩阵的元素和。然后用O(n^5)的复杂度枚举所有的立方体，将底面缩为一个点，对剩下一维作为一维处理。hoj 2555