最近看DP的题目比较多，感觉真是递归之后的又一大神器啊。
题目是这样的：http://ac.jobdu.com/problem.php?pid=1139
已知矩阵的大小定义为矩阵中所有元素的和。
给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如，如下4 * 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。
最开始我的分析是这样的：要确定一个矩阵至少得4个元素，即4个角；或者起始坐标以及长度宽度。我们可以遍历每个顶点以及每种边长。
可是这样的复杂度简直是爆炸的。
直觉告诉我，只能用动态规划了。
因为动态规划可以把复杂的问题划分成很小的部分。
那么问题来了，这个问题的子问题是什么？
其实找到子问题是解题思路里面最重要的部分。
我们之前碰到的一个问题是，求一维数组里面的最大和。感觉这里可以用，又不知道怎么用。
我们上面说到了，确定一个子矩阵得至少4个元素，那假设我们已经知道了其中的两个：
假设最优解在第j行和第i行之间，剩下的就是去确定两个列了。
既然我们已经把解的范围局限在i，j两行之间了，我们真的需要去求具体的哪一列吗？
先这样看，如果i，j相等的话，也就是解在同一列。这样的话，问题是不是就转换为求一维数组的最大和了呢？
扩展到一般情况：i，j不想等：比如两行为：
1 2 -3 -4
-5 7 2 3
那么我们如何求呢？
降维！
我们把每一列压缩为一个数，然后求一维的最大和就ok了。
整理一下思路：
1，我们遍历所有的 行 的组合情况，即第i行到第j行的所有情况。
2，然后对每个组合之间的两行之间的元素求这一列的值
3，对一个一维的和数组求最大和
4，对上述的最大和求最大值
在具体实现的时候，我们定住第i行不动，移动第j行，然后不断的求两行之间的每一列的和（压缩）。
然后在每次移动i的时候，我们清空储存列的和的数组。
程序：
//我们有第i行到第j行，然后求出每一列的从i到j的和，转化为一维数组，然后求这个数组的最大和
#include <iostream>
#include <cstring>
int maxSubArray(int* a,int n)//一维数组的最大和
{
if(!a||n<=0)
return 0;
int curmax=0,max=0;
max=curmax=a[0];
for(int i=1;i<n;i++)
{
if(curmax>=0)
{
curmax+=a[i];
}
else
curmax=a[i];
if(curmax>max)
max=curmax;
}
return max;
}
int maxSumInMatrix(int a[200][200],int n)
{
int i=0,j=0,k=0;
int sumij[200]={0};//从i到j的每一列的和
int max_n=a[0][0],max=a[0][0];
for(i=0;i<n;i++)
{
memset(sumij,0,sizeof(sumij));//clear，每次移动i的时候清除
for(j=i;j<n;j++)
{
for(k=0;k<n;k++)
{
sumij[k]+=a[j][k];
}
max_n=maxSubArray(sumij,n);
if(max_n>max)//检查并更新最大值
max=max_n;
}
}
return max;
}
int main()
{
int a[200][200];
memset(a,0,sizeof(a));
int n;
std::cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
std::cin>>a[i][j];
}
std::cout<<maxSumInMatrix(a,n);
}
