51nod 最大子矩阵和(动态规划)

时间:2022-05-08 09:01:19
最大子矩阵和

一个M*N的矩阵,矩阵中有一些整数(有正有负),找到此矩阵的一个子矩阵,并且这个子矩阵的元素的和是最大的,输出这个最大的值。

输入
第1行:M和N,中间用空格隔开(2 <= M,N <= 500)。
第2 - N + 1行:矩阵中的元素,每行M个数,中间用空格隔开。(-10^9 <= M[i] <= 10^9)
输出
 
输出和的最大值。如果所有数都是负数,就输出0。
 
输入示例
3 3
-1 3 -1
2 -1 3
-3 1 2
输出示例
7
 
请选取你熟悉的语言,并在下面的代码框中完成你的程序,注意数据范围,最终结果会造成Int32溢出,这样会输出错误的答案。
不同语言如何处理输入输出,请查看下面的语言说明。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
using namespace std ;
int n,m,a[][],dp[];long long b[];
long long DP(long long c[])
{
long long sum=,maxnn=;
for(int l=;l<m;l++)
{
sum += c[l];
if (sum < )sum = ;
if (sum > maxnn)maxnn = sum;
}
return maxnn;
}
int main()
{
cin>>m>>n;
for(int i=;i<n;i++)for(int j=;j<m;j++)cin>>a[i][j];
long long maxn=;
for(int i=;i<n;i++)
{memset(b,,sizeof(b));
for(int j=i;j<n;j++)
{ for(int k=;k<m;k++)
{
b[k]+=a[j][k];
}
long long s=DP(b);
maxn=max(maxn,s);
}
}
cout<<maxn<<endl;
return ;
}