[菜鸟日记]前缀和之子矩阵最大值

前缀和求矩阵子矩阵元素最大和

emmm很早之前我看这道题是直接放弃的，最近看了一下前缀和，对这道题重新进行了理解。
然后大概看了看别人的博客，结合自己的的理解，大概会做了。
题目链接：SWUST OJ 130
大概思路：

对于这样一个矩阵，最大的矩形前缀和就等于蓝的矩阵加上绿的矩阵，再减去重叠面积，最后加上小方块，即

sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j]；
我们就可以进行预处理：

for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }

然后，枚举每一个子块，这里需要用到4重循环，很暴力是不是…
完整代码如下：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<string>
#define M 4505
#define N 125
const int inf=0x3f3f3f3f;
using namespace std;
int sum[N][N];
int main(){
    int a[N][N],n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
    int tol=-inf,ans=-inf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=i;k<=n;k++){
                for(int x=j;x<=n;x++){
                    tol=sum[k][x]-sum[i-1][x]-sum[k][j-1]+sum[i-1][j-1];
                    ans=max(ans,tol);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

这种方法太暴力了…我还不会更简单的…还是菜啊。