#include <iostream>
#include <fstream>
using namespace std;
short arr[100][100];
int getSum(int left,int right,int up,int bottom)
{
	int s(0);
	for(int i=left;i<=right;++i)
	{
		for(int j=up;j<=bottom;++j)
		{
			s += arr[i][j];
		}
	}
	return s;
}
int main()
{
	int n;
	int m;
	short num;
	int sum(-1270);
	int s;
	int lastSum = 0;
	int tempSum = 0;
	int left,right,up,bottom;
	//ifstream in("in.txt");
	cin>>n;
	m = n*n;
	/*输入*/

	for(int rr = 0;rr<n;++rr)
	{
		for(int c =0;c<n;++c)
		{
			cin>>num;
			arr[rr][c] = num; 
		}
	}

	for(int r = 0;r<n;r++)
	{
		for(int i=0;i<n;i++)
		{
			s = getSum(i,i,r,r);//计算子矩形的和，控制在一维
			if(s > sum)
			{
				sum = s;
			}
			for(int col = i+1;col<n;++col)
			{
				lastSum = getSum(i,col,r,r);
				for(int row = r+1;row<n;row++)
				{
					//cout<<i<<'\t'<<col<<'\t'<<r<<'\t'<<row<<endl;
					tempSum = getSum(i,col,row,row);
					lastSum += tempSum;

					if(lastSum > sum)
					{
						sum = lastSum;
					}
				
				}
			}
		}
	}
	
	cout<<sum<<endl;
	
	return 0;
}

• 这个应该是O(N^6)了吧？？！ (23) jimi 2007-09-21 16:14:38
• Re:求大虾帮帮看下程序，虽说是O(N^4)但是，已经精简过，在N^3与N^4之间，为什么还TLE? (47) pengfei 2007-10-12 15:44:52