UVa 108: Maximum Sum

這道題用暴力解法+動態規劃。分析如下：

對於某個1*m的矩陣，即一個數列，求其maximal sub-rectangle，可以通過求最大長連續字串和來求得（這個用到了動態規劃）。

那麼對於n*m的矩陣，將每列的各個數字求和，將得到一個1*m的矩陣，用上文所說的方法求得的最大和即為該n*m矩陣的所有行數為n的子矩陣中的最大子矩陣和。

那麼這道題，通過枚舉所有行數為1、2、3.....N 的矩陣（暴力），分別用上述方法壓縮矩陣求最大連續字串和，找出其中最大值，即為所求結果。

我的解題代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;

int table[100][100];
int sum[100];
int N;

int max_continuous_sum()
{
	int maxs=0,s=0;
	for(int i=0; i<N; i++)
	{
		if(s>=0) s+=sum[i];
		else s=sum[i];
		maxs = maxs>s ? maxs : s;
	}
	return maxs;
}
int main()
{
	cin >> N;
	int maxsum=0;
	int tmp;
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			cin >> table[i][j];
			sum[j]=table[i][j];
		}
		tmp = max_continuous_sum();
		maxsum = maxsum>tmp ? maxsum : tmp;
		for(int j=i-1; j>=0; j--)
		{
			for(int k=0; k<N; k++)
				sum[k]+=table[j][k];
			tmp = max_continuous_sum();
			maxsum = maxsum>tmp ? maxsum : tmp;
		}
	}
	cout << maxsum << endl;
	return 0;
}