1051 最大子矩阵

1051 最大子矩阵和

一个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示例

Output示例

7

思路：我们枚举每一列的前i行(1<=i<=n)和，问题就变成最大连续子序列和了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a[503][503];
 5 ll b[503];
 6 ll c[503];
 7 int n,m;
 8 ll dp()
 9 {
10     ll MMax=b[m];
11     c[m]=b[m];
12     for(int i=m-1;i>=1;i--)
13     {
14         c[i]=max(c[i+1]+b[i],b[i]);//转移方程相当于我以i为起点的最大序列是多少//
15         MMax=max(MMax,c[i]);
16     }
17     return MMax;
18 }
19 ll hh()
20 {
21     ll Max=-1e18-10;
22     for(int i=1;i<=n;i++)
23     {
24         memset(b,0,sizeof(b));
25         for(int j=i;j<=n;j++)//z在这相当于构造了所有的子矩阵//
26         {
27             for(int k=1;k<=m;k++)
28             {
29                 b[k]+=a[j][k];
30             }
31             ll sum=dp();
32             Max=max(sum,Max);
33         }
34     }
35     return Max;
36 }
37 int main()
38 {
39 
40         scanf("%d%d",&m,&n);
41         for(int i=1;i<=n;i++)
42             for(int j=1;j<=m;j++)
43             scanf("%I64d",&a[i][j]);
44         ll x=hh();
45         if(x<0) cout<<0<<endl;
46         else cout<<x<<endl;
47     return 0;
48 }