求子矩阵最大累加和

本文主要是介绍求子矩阵最大累加和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目如下：

输入在一行给出两个数n,m，代表矩阵的行和列。而后n行，每一行给出m个数，数值有正有负，也可能是0。

输出在一行给出子矩阵的最大累加和。

给出一个案例。

输入：

3 3
-90 48 78 
64 -40 64
-81 -7 66

输出：

209 （48+78-40+64-7+66=209）

整体思路是定义一个起始行，对该行开始往后的每一个矩阵进行竖向求和，而后将其转换为求最大子序列和的问题，时间复杂度为n^3，细节见代码：

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];//范围根据实际题目开稍大一些就好啦
int sum[1005];
int maxAdd(int sum[],int n);
int main() {
	int n,m,ans;
	cin >> n >> m;
	for(int i=0;i<n;i++) 
		for(int j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	int beginRow = 0;//每一行都要成为一次开始行 
	while(beginRow<n) {
		for(int i=beginRow;i<n;i++) { 
			for(int j=0;j<m;j++)
				sum[j] += a[i][j];//利用累加的性质，每累加一次就是对生成矩阵的竖向求和，这样就可以将问题转换为就最大子序列和 
			ans = max(ans,maxAdd(sum,m));//求最大子序列和 
		}
		memset(sum,0,sizeof(sum));
		beginRow++;
	}
	cout << ans;
	return 0;
}

int maxAdd(int sum[],int n) {
	int ans = -0x7fffffff,s = 0;
	for(int i=0;i<n;i++)
		ans = max(ans,sum[i]);
	if(ans<0) return ans;
	else {
		for(int i=0;i<n;i++) {
			s += sum[i];
			if(s<0) s = 0;
			else ans = max(s,ans);
		}
		return ans;
	}
}

这篇关于求子矩阵最大累加和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！