洛谷 P1719 最大加权矩形

使用前缀和进行数据的预处理

再使用遍历查找最大加权矩形

#include<bits/stdc++.h>
using namespace std;
int b[125][125];

int main(){
//初始化最小值
    int n,ans=-99999999;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a;
            cin>>a;
//此时每一列的对应数值，为其前n项的前缀和
            b[i][j] = b[i-1][j]+a;
        }
    }
//进行遍历
    for(int i=1;i<=n;i++){
//i遍历区间结尾
        for(int j=0;j<i;j++){
//j遍历区间开头
            int sum = 0;
            for(int k=1;k<=n;k++){
//k为对应行数
//tmp为k列从j到i区间的和
                int tmp = b[i][k]-b[j][k];
//判断当前和是否小于零，如果小于零，就将sum重置
                if(sum<0){
                    sum = 0;
                }
//将当前列取得的区间加到sum中
                    
                sum+=tmp;
//如果sum大于ans，就刷新
                
                if(sum>ans){
                    ans = sum;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}