#include <iostream>
using namespace std;
short MaxSum(short *colSum, int n)
{
	int maxSum = 0;
	int b=0;
	int i=0;
	for (i; i<=n-1; i++)
	{
		if (b>0)
		{
			b+=colSum[i];
		}
		else
		{
			b = colSum[i];
		}
		if (b > maxSum)
		{
			maxSum = b;
		}
	}
	return maxSum;
}


int main()
{
    const short N = 100;
	short matrix[N][N];
	short colSum[N]={0};

	int i,j,k;
	int n;
	cin>>n;
	
    for (i=0; i<=n-1; i++)
	{
		for (j=0; j<=n-1; j++)
		{
			cin>>matrix[i][j];
		}	
	}


	int maxSubSum = 0;
	for (i=0; i<=n-1; i++)
	{
		for (k=0; k<=n-1; k++)
		{
			colSum[k] = 0;
		}
		for (j=i; j<=n-1; j++)
		{
			int maxTemp;
			for (k=0; k<=n-1; k++)
			{
				colSum[k] += matrix[j][k];
			}
			maxTemp = MaxSum(colSum, n);
			if (maxTemp > maxSubSum)
			{
				maxSubSum = maxTemp;
			}
		}
	}

	cout<<maxSubSum<<endl;
    return 0;
}

• Re:用动态规划,就是n^3 (1076) seu_enic 2009-03-02 19:00:05
  • 你的是暴力,当然是n^4,我的和你的差远了,我的是DP呀,最深的一层只有n^3,所以就是n^3 (0) gfedcba 2009-03-02 20:45:08
  • Re:用动态规划,就是n^3 (12) 527554192 2010-08-09 19:42:37
• Re:用动态规划,就是n^3 (1040) shenmeng1987 2009-04-15 14:48:54