最近看DP的題目比較多，感覺真是遞歸之后的又一大神器啊。
題目是這樣的：http://ac.jobdu.com/problem.php?pid=1139
已知矩陣的大小定義為矩陣中所有元素的和。
給定一個矩陣，你的任務(wù)是找到最大的非空(大小至少是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個角；或者起始坐標以及長度寬度。我們可以遍歷每個頂點以及每種邊長。
可是這樣的復(fù)雜度簡直是爆炸的。
直覺告訴我，只能用動態(tài)規(guī)劃了。
因為動態(tài)規(guī)劃可以把復(fù)雜的問題劃分成很小的部分。
那么問題來了，這個問題的子問題是什么？
其實找到子問題是解題思路里面最重要的部分。
我們之前碰到的一個問題是，求一維數(shù)組里面的最大和。感覺這里可以用，又不知道怎么用。
我們上面說到了，確定一個子矩陣得至少4個元素，那假設(shè)我們已經(jīng)知道了其中的兩個：
假設(shè)最優(yōu)解在第j行和第i行之間，剩下的就是去確定兩個列了。
既然我們已經(jīng)把解的范圍局限在i，j兩行之間了，我們真的需要去求具體的哪一列嗎？
先這樣看，如果i，j相等的話，也就是解在同一列。這樣的話，問題是不是就轉(zhuǎn)換為求一維數(shù)組的最大和了呢？
擴展到一般情況：i，j不想等：比如兩行為：
1 2 -3 -4
-5 7 2 3
那么我們?nèi)绾吻竽兀?br> 降維！
我們把每一列壓縮為一個數(shù)，然后求一維的最大和就ok了。
整理一下思路：
1，我們遍歷所有的 行 的組合情況，即第i行到第j行的所有情況。
2，然后對每個組合之間的兩行之間的元素求這一列的值
3，對一個一維的和數(shù)組求最大和
4，對上述的最大和求最大值
在具體實現(xiàn)的時候，我們定住第i行不動，移動第j行，然后不斷的求兩行之間的每一列的和（壓縮）。
然后在每次移動i的時候，我們清空儲存列的和的數(shù)組。
程序：
//我們有第i行到第j行，然后求出每一列的從i到j(luò)的和，轉(zhuǎn)化為一維數(shù)組，然后求這個數(shù)組的最大和
#include <iostream>
#include <cstring>
int maxSubArray(int* a,int n)//一維數(shù)組的最大和
{
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(luò)的每一列的和
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);
}
