503a – 最大子阵

给定一个 n×m 的矩阵 A，求 A 中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A 的子矩阵指在 A 中行和列均连续的一部分。

蓝桥 – T118 试题 历届试题 最大子阵

资源限制

时间限制：1.0s   内存限制：256.0MB

输入格式

输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。
接下来n行，每行m个整数，表示矩阵A。

输出格式

输出一行，包含一个整数，表示 A 中最大子矩阵的元素和。

样例输入

3 3
2 -4 1
-1 2 1
4 -2 2

样例输出

6

代码实现

#include <iostream>
#include <string.h>
using namespace std;

long long MaxSub(long long arr[],int n){
	long long b = 0;
	long long sum = -1000000000; 
	for(int i = 0;i < n;i++){
		if(b + arr[i] < arr[i]){
			b = arr[i];
		}else{
			b = b + arr[i];
		}
		if(sum < b){
			sum = b;
		}
	}
	return sum;
} 

long long rec[510] = {0};
int tab[510][510] = {0};

int main(){
	
	int n,m;
	cin>>n>>m;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			int t;
			cin>>t;
			tab[i][j] = t;
		}
	}
	long long maxx = -100000000;
	for(int i = 0; i < n;i++){
		memset(rec,0,sizeof(rec));
		for(int j = i; j < n;j++){
			for(int k = 0;k < m;k++){
				rec[k] += tab[j][k];
			}
			long long t = MaxSub(rec,m);
			if(t > maxx){
				maxx = t;
			}
		}
	}
	cout<<maxx;
	return 0;
}