题解 | #To the Max#

题目大意：
给你一个矩阵
让你求长宽无限制的最大矩阵和

思路：
对于二维数组我们可以这样考虑
a[1][1],a[1][2],a[1][3]······
a[2][1],a[2][2],a[2][3]······
a[3][1],a[3][2],a[3][3]······、
a[j][1],a[j][2],a[j][3]······
我们设i<j，则我们可以转化第i行到第j行的二维数组为一维数组
把相同列的数字都加起来
即{a[i][1]+a[i][2]······,a[i+1][1]+a[i+1][2]······,a[j][1]+a[j][2]······}
那么问题就转化一维数组成了求最大子段和
然后直接套最大子段和求就好啦

#include <iostream>
#include <string.h>
using namespace std;
int a[105][105];
int sum[105];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cin>>a[i][j];
    }
    int ans=-1e9;
    for(int i=1;i<=n;i++){
        memset(sum,0,sizeof(sum));
        for(int j=i;j<=n;j++){//i到j行
            for(int k=1;k<=n;k++)sum[k]+=a[j][k];//相同列都加起来
            int cnt=0;
            for(int k=1;k<=n;k++){
                if(cnt<=0)cnt=0;
                cnt+=sum[k];
                if(cnt>ans)ans=cnt;
            }
        }
    }
    cout<<ans;
    return 0;
}