51Nod - 1051 最大子矩阵和(dp)

本文主要是介绍51Nod - 1051 最大子矩阵和(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。 例如：3*3的矩阵：

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

和最大的子矩阵是：

3 -1
-1 3 1 2

Input

第1行：M和N，中间用空格隔开（2 <= M,N <= 500)。 第2 - N +
1行：矩阵中的元素，每行M个数，中间用空格隔开。(-10^9 <= M[i] <= 10^9)

Output

输出和的最大值。如果所有数都是负数，就输出0。

Input示例

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

Output示例

7

思路

已经知道了一维的最大字段和的求法，求二维只需要枚举每一个行和列，把二维转化成一维，然后就是求最大字段和了，更新最大值，复杂度$O(n^3)$

思路

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const ll N=1e3+10;
ll a[N][N],b[N];
int main()
{ll n,m;scanf("%lld%lld",&m,&n);for(ll i=1; i<=n; i++)for(ll j=1; j<=m; j++)scanf("%lld",&a[i][j]);ll maxx=0;for(ll i=1; i<=n; i++){mem(b,0);for(ll j=i; j<=n; j++){ll sum=0;for(ll k=1; k<=m; k++){b[k]+=a[j][k];sum+=b[k];if(sum<0)sum=0;maxx=max(maxx,sum);}}}printf("%lld\n",maxx);return 0;
}

这篇关于51Nod - 1051 最大子矩阵和(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---