Lut本科回忆录

蒻苟的学习记录

题目：给定一个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;
}