/*
题目大意：给你一个n*n的矩阵，让你找一个子矩阵，使得这个矩阵内所有数字的和最大。 
解题思路：先联系一维的最大连续子串和，dp[i]=max(dp[i-1],0)+a[i],
其中dp[i]表示前面i项内所取得的最大值。
这个二维矩阵的题目也可以进行转换。先用mpt[i][j]，表示第i行前j列的和。
那么状态转移方程可以转换为dp[k]=max(dp[k-1],0)+a[k]，
我们可以将a[k]看作第j列到第i列的第k项的和，a[k]=mp[k][i]-mp[k][j-1]。
*/
#include<iostream>
#include<cstdio>
using namespace std;
int mpt[102][102];
int main()
{
	int n,i,j,k,a;
	while(scanf("%d",&n)!=EOF)
	{
		//转化：使mpt[i][j]表示第i行前j列的和。
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%d",&a);
				mpt[i][j]=mpt[i-1][j]+a;
			}
			//Dp。
			int ans=-1,sum;
			for(j=1;j<=n;j++)
				for(i=j;i<=n;i++)//第j行到第i行。
				{
					sum=0;
					for(k=1;k<=n;k++) //看成一维的 dp[k]=max(dp[k-1],0)+a[k]。
					{
						a=mpt[i][k]-mpt[j-1][k];
						sum+=a;
						if(sum<0) sum=0;
						if(sum>ans) ans=sum;
					}
				}
				cout<<ans<<endl;
	}
	return 0;
}

• 解释没看明白，另外全负的数据通不过 (2) wisatbff 2014-06-16 22:53:17