首先还是对题目的意思进行说明，给出一个矩阵的数，然后求出一个子矩阵这个子矩阵包含的数的和是最大的。
首先对于题目进行转化，利用一个数组add进行存放临时数据，第一行存放原来数据的第一行，第二行存放原来数据的一二行的和，第三行存放原来数据的一二三行的和。
利用这个数组可以把任何连续几行的数据变成一行的数据，然后对于一行的数据进行求最大来求出原矩阵和的最大。
对于一行数据我们就可以进行dp了。
动态方程（这里就不是转移方程了，他没有状态的转化）
if(row_max > 0)
row_max += now;
else
row_max = now;
if(row_max > result)
result = row_max;
什么意思呢？解释一下，一旦当前是负数，那么一定是不能往上加的，因为加的那个数无论是正的还是负的，都变加的那个数小，还不如直接用那个数开始呢。如果是正数，那么老老实实往上加对了，反正是要求是连续的，加了这个也不一定会更新最大值，加了这个再加下一个就有可能更新最大值了。
初始值0就不多说了，反正肯定会更新的。
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; /*dp，poj1050*/ int maps[105][105];//记录用户输入数据 int add[105][105];//记录1行到当前行的和 /* 利用add数组可以求出任意两行同一列下连续的和 123 456 789 如：求2-3行的和，为add[3][0]-add[1][0] 注意add保存的是原始数据求和之后的值 add[3][0]=map[3][0]+map[2][0]+map[1][0]; */ int main() { int n;//用户输入变量 int i,j,k;//循环变量 int result;//结果 int now;//当前值 int row_max;//当前行最大值 cin>>n; result = -100000;//初始化 for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { cin>>maps[i][j]; add[i][j] = maps[i][j] + add[i-1][j]; //生成add } } for (i = 1; i <= n; i++) { for (k = i; k <= n; k++) { row_max = 0; for (j = 1; j <= n; j++) { //计算从i行到k行的和 now = add[k][j] - add[i-1][j]; //下面三句是dp重点，如果看不懂先记住再说 if(row_max > 0) row_max += now; else row_max = now; if(row_max > result) result = row_max; } } } cout<<result<<endl; return 0; }