> #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;
> }

我就是问为什么这个程序是O(n^3)的。。。我也是这样写的。。。

• 你的是暴力,当然是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