51 Nod1051 最大子矩阵和

Problem

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

例如：3*3的矩阵：

-1 3 -1

2 -1 3

-3 1 2

和最大的子矩阵是：

3 -1

-1 3

1 2

Solution

枚举上下边界，竖着加起来，横向算最大字段和。

Code

#include<stdio.h>
#include<set>
//#include<iostream>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
//#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int m,n;
ll a[520][520];
ll f[520];
ll sum[520][520];
ll mx=0;
int main() {
    //io_opt;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lld",&a[i][j]);
            sum[i][j]=sum[i-1][j]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=1;k<=m;k++){
                f[k]=max(0LL,f[k-1]+sum[j][k]-sum[i-1][k]);
                mx=max(mx,f[k]);
            }
        }
    }
    printf("%lld\n",mx);
    return 0;
}