(三) POJ1050，动态规划必做题目，经典程度五颗星。这个题目的前身就是：求最大子序列和。
先来看最大子序列和。有一串数，有正有负，如2，-1，5，4，-9，7，0，3，-5。求：这一串数中，和最大的一段。比如说，从第一个数2开始，发现下一个为-1，加下-1后和显然会变小。再往后看，第三个数是5，所以上一个-1还是要选的，这样才能加上5。哎，不看了，这样求最大和还不得累死。嘿嘿，这时DP就派上用场了。
设这串数为X1 X2 X3 … Xn, 用dp(i,j)表示从Xi…Xj的最大子序列和。
按照DP的思路，想办法减小问题的规模。有n个数，怎样能减少到n-1数？想办法把最后一个数Xn去掉，问题规模就能减少到n-1。
通过观察可以发现：X1…Xn的最大子序列可以分为两类：以Xn结尾、不以Xn结尾。不以Xn结尾的最大子序列，其实就是X1…Xn-1的最大子序列，发现这点很重要。
这样就有：dp( i, j ) = Max( dp( i, j-1 ), Last( j ) ).其中Last( j )表示以Xj结尾的最大子序列的和。
功夫不负有心人，终于把问题规模减少了。但是，一波未平一波又起，新的问题又出现了。Last( j )如何求？即，求以Xj结尾的最大子序列的和。再用DP求解。
Last( j )和Last( j-1 )之间的关系比较简单。Last(j )的值里面必然会包括Xj的值，到底有没有Last( j-1 )也很简单，主要取决于Last( j-1 )是正还是负。
这样就有：Last( j ) = Max( Xj, Last( j-1) + Xj );
状态转换方程：
dp( i, j ) = Max( dp( i, j-1 ), Last( j ) )其中：dp(i,j)表示从Xi…Xj的最大子序列和
Last( j ) = Max( Xj, Last( j-1 ) + Xj ); 其中：Last( j )表示以Xj结尾的最大子序列的和
现在，回到POJ1050。想想能不能利用上面的结果？求最大子矩阵，那么只要确定了子矩阵有几行、几列即可。这样，可以枚举子矩阵的行数和列数。
比如，当子矩阵只要一行时，那么只关心它的列从哪开始到那结束就行。哦，这其实就是一个最大子序列和的问题。这一行就是这一串数，求和最大的一段。那么当子矩阵有两行时，怎么办？如何把两行变为一行？一个聪明的想法就是：把这两行按照对应的列加起来。
好了问题已经漂亮的解决了：在原矩阵中任意画出一部分，然后按照对应的列加起来，问题就转变为一个最大子序列和的问题
//下面的是 一维数组 ，最大长序列 的和 最大子串和:
import java.util.Arrays; /* 其实就是最大子段和问题在二维空间上的推广。先说一下一维的情况吧：设有数组a0,a1…an,找除其中连续的子段，使它们的和达到最大。假如对于子段：9 2 -16 2 temp[i]表示以ai结尾的子段中的最大子段和。在已知temp[i]的情况下，求temp [i+1]的方法是： 如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段)，也就是说 状态转移方程： temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i]; 对于刚才的例子 temp： 9 11 -5 2，然后取temp[]中最大的就是一维序列的最大子段。求一维最大子段和的函数： import java.util.Arrays; /* 其实就是最大子段和问题在二维空间上的推广。先说一下一维的情况吧：设有数组a0,a1…an,找除其中连续的子段，使它们的和达到最大。假如对于子段：9 2 -16 2 temp[i]表示以ai结尾的子段中的最大子段和。在已知temp[i]的情况下，求temp [i+1]的方法是： 如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段)，也就是说 状态转移方程： temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i]; 对于刚才的例子 temp： 9 11 -5 2，然后取temp[]中最大的就是一维序列的最大子段。求一维最大子段和的函数： */ public class TheMaxSubString { public static void main(String[] args) { // int [] buff ={1,-1,3,4,5,6,7,8,-1,128}; int[] buff = { 4, 9, -17, 7 }; System.out.println(Arrays.toString(buff)); System.out.println(DpLineMaxSum(buff, 4)); int[][] buff2 = { { 0, -2, -7, 0 }, { 9, 2, -6, 2 }, { -4, 1, -4, 7 }, { -1, 8, 0, -2 } }; System.out.println(DpMatrixMaxSum(buff2, 4, 4)); } // 最大矩阵和：二维数组 public static int DpMatrixMaxSum(int buff[][], int row, int col) { int maxSum = 0; int virtualLine[] = new int[col]; // 从哪一行开始往下求和 for (int i = 0; i < row; i++) { // 以i行为基准，需要循环多少次，求 for (int temp = 0; temp < row - i; temp++) { int j = i + temp;// 以i为基准啊进行往下求和 for (int column = 0; column < col; column++) { int sum = 0; // 按照列进行相加， for (int k = i; k <= j; k++) { sum += buff[k][column]; } virtualLine[column] = sum; } int value = DpLineMaxSum(virtualLine, col); maxSum = (maxSum < value) ? value : maxSum; } } return maxSum; } // 最大子串和:一维数组 public static int DpLineMaxSum(int buff[], int n) { int e = 0; int max = 0; int[] temp = Arrays.copyOf(buff, n); for (int i = 1; i < n; i++) { temp[i] = (temp[i - 1] > 0 ? temp[i - 1] : 0) + buff[i]; if (max < temp[i]) { max = temp[i]; e = i; } } System.out.println("line-->" + e); return max; } }