最大矩阵和

蒻苟的学习记录

题目：给定一个n✖n大小的矩阵，求其中子矩阵的和最大值（来自洛谷p1719）

求一个方向上的前缀和，该方法计算矩阵竖直方向上的前缀和 a[i][j]=a[i-1][j]+x ，然后用 i 和 j 确定子矩阵行坐标的范围，即第 j 行到第 i 行，然后再循环一个k来计算子矩阵内从第1列到第k列的和，若和为负值了就重新计算子矩阵（当然本道题的限制是答案是正数，若要突破这个限制，即把判断sum<0改成sum<ans就行啦）

#include <bits/stdc++.h>
#define N 10010
#define rep(i,a,b)  for(int i=a;i<=b;++i)  
using namespace std;
typedef long long ll;
int a[N][N],s[N][N],n,ans=-0x3f3f3f3f;
int main()                //初始ans为极小值
{
    cin>>n;
    rep(i,1,n){
        rep(j,1,n){
            int x;
            cin>>x;
            a[i][j]=a[i-1][j]+x;
        }   //累加竖直方向上的前缀和
    }
    rep(i,1,n){
        rep(j,0,i-1){
            int sum=0;
            rep(k,1,n){   //循环加j到i行之间的子矩阵和，
                sum+=a[i][k]-a[j][k];  
                if(sum<0)sum=0;    //如果和小于0则初始化sum
                ans=max(ans,sum);
            }
        }
    }
    cout<<ans;
}