UVA 108: Maximum Sum

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=44&mosmsg=Submission+received+with+ID+8683782

题目大意：

      一个二维矩阵求哪个子矩阵的和最大，输出最大值。

解题思路：

      由于是二维矩阵，如果枚举的话复杂度很高。一维的连续子串的最大和问题有个很好的O(n)算法，我们能不能把二维的转化成一维的来做呢？答案是肯定的。我们通过预处理把当前行里面的数存的是同一列前面行全部数的加上自己的和，要得到某列某两行之间数的和就直接两行的数之差，就转化成一个一维数组，每个这样的一维数组求最大值就是答案。

解题代码：

#include<iostream>
using namespace std;
int a[200][200],tmp[200];
int n;
int maxv(int *s){
	int max=-10000000;
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=s[i];
		if(sum>max) max=sum;
		if(sum<0)sum=0;
	}
	return max;
}
void input(){
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			cin>>a[i][j];
			if(i!=0){
				a[i][j]+=a[i-1][j];
			}
		}
}
int work(){
	int max=-1000000;
	for(int i=0;i<n;i++)
		for(int j=-1;j<i;j++){
			for(int k=0;k<n;k++)
				if(j==-1)
				  tmp[k]=a[i][k];
				else
					tmp[k]=a[i][k]-a[j][k];
			int p=maxv(tmp);
			if(p>max) max=p;
		}
	return max;
}
int main(){
	while(cin>>n){
		input();
		cout<<work()<<endl;
	}
}

扩展知识：http://linjiazhen.is-programmer.com/admin/drafts/25634/edit

• 全局相关文章
• 相关文章