最大子矩阵和

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

  • 思路
    最后子矩阵一定是在某两行之间的。假设我们认为子矩阵在第i行和第j列之间,枚举所有1<=i<=j<=M,表示最终子矩阵选取的行范围。
    我们把每一列第i行到第j行之间的和求出来，形成一个数组c,于是一个第i行到第j行之间的最大子矩阵和对应于这个和数组c的最大子段和。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for i = 1 to M do
        for j = i to M do
             //计算第每列第i行到第j列的和
             for k = 1 to N do
                c[k] = (j == i)?a[i][k] : (c[k] + a[j][k])
             endfor
             //求c的最大子段和 记录全局最优结果
        endfor
    endfor

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
     
    using namespace std;
    long long a[550][550];
    int main()
    {
        int N,M,t;
        long long sum,ans=0;
        scanf("%d %d",&M,&N);
        memset(a,0,sizeof(a));
        for(int i=1;i<=N;i++){
            for(int j=1;j<=M;j++){
                scanf("%d",&t);
                a[i][j]=a[i-1][j]+t;
            }
        }
        for(int i=1;i<=N;i++){
            for(int j=i;j<=N;j++){
                sum=0;
                for(int k=1;k<=M;k++){
                    sum=sum+(a[j][k]-a[i-1][k]);
                    if(sum<0) sum=0;
                    if(sum>ans) ans=sum;
                }
            }
        }
        printf("%lld\n",ans);
        return 0;
    }