首页 > 其他 > 详细

最大子矩阵和

时间:2020-08-22 12:38:54      阅读:67      评论:0      收藏:0      [点我收藏+]

http://ybt.ssoier.cn:8088/problem_show.php?pid=1224

类似最大子段和

枚举矩阵的左端点i和右端点j

将每一行的i到j之间的区间和(前缀和求出)视为一个元素,求由它们构成的数列中的最大子段和

时间复杂度o(n^3)

#include<bits/stdc++.h>
using namespace std;
int a[110][110],s[110][110];
int main()
{
	memset(s,0,sizeof(s));
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	s[i][j]=s[i][j-1]+a[i][j];
	int maxn=-100000,sum;
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
	{
		sum=0;
		for(int k=1;k<=n;k++)
		{
			sum=max(sum+s[k][j]-s[k][i-1],s[k][j]-s[k][i-1]);
			maxn=max(maxn,sum);
		}
	}
	cout<<maxn;
	return 0;
}```

最大子矩阵和

原文:https://www.cnblogs.com/qwq-/p/13544877.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!