思路：
首先你可能会想到穷举的方法，但当n很大时，显然是不可取的。。这个题应该是用dp来解决的。
让我们先来看另外的一个问题(最大子段和问题)： 给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i
[cpp]?
int maxSubArray(int n,int a[])?
?{?
???? int b=0,sum=-10000000;?
???? for(int i=0;i
????????? if(b>0) b+=a[i];?
????????? else b=a[i];?
????????? if(b>sum) sum=b;???
???? }?
???? return sum;?
?}//动态规划。?
联系本题，二者区别呢？一个是一维的，一个是多维的，那么把多维转化为一维不就可以ac了。。
?假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵，如下所示(ari表示a[r][i],假设数组下标从1开始)：
? | a11 …… a1i ……a1j ……a1n |
? | a21 …… a2i ……a2j ……a2n |
? |? .???? .???? .??? .??? .???? .??? .?? |
? |? .???? .???? .??? .??? .???? .??? .?? |
? | ar1 …… ari ……arj ……arn |
? |? .???? .???? .??? .??? .???? .??? .?? |
? |? .???? .???? .??? .??? .???? .??? .?? |
? | ak1 …… aki ……akj ……akn |
? |? .???? .???? .??? .??? .???? .??? .?? |
? | an1 …… ani ……anj ……ann |
?那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下：
?(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
?由此我们可以看出最后所求的就是此一维数组的最大子断和问题，到此我们已经将问题转化为上面的已经解决了的问题了。
nyoj 和 poj 题目基本一样，只是输入格式 有区别，这里只给出 nyoj 的 代码。。
[cpp]
??
#include
#include
int ans[200][200];?
int n,m,max;?
void find (int k)?
{?
??? for(i=1;i<=m;i++)?
??? {?
??????? if(t>0)?
??????????? t+= ans[k][i];?
??????? else?
??????????? t= ans[k][i];?
??????? if(t>max)?
??????????? max=t;?
??? }?
}?
int main()?
{?
??? int a,b,c,ncase;?
??? scanf("%d",&ncase);?
??? while(ncase--)?
??? {?
??????? scanf("%d%d",&n,&m);?
??????? for(a=1;a<=n;a++)?
??????? {?
??????????? for(b=1;b<=m;b++)?
??????????????? scanf("%d",&ans[a][b]);?
??????? }?
??????? max=ans[1][1];?
??????? for(a=1;a<=n;a++)?
??????? {?
??????????? find(a);?
??????????? for(b=a+1;b<=n;b++)?
??????????? {?
??????????????? for(c=1;c<=m;c++)?
??????????????? {?
??????????????????? ans[a][c]+=ans[b][c];?
??????????????? }?
??????????????? find(a);?
??????????? }?
??????? }?
??????? printf("%d\n",max);?
??? }?
}?????????
作者：PIAOYI0208