蓝桥杯历届试题-最大子阵

解题思路:一维和加最大子串和

注意事项:

参考代码:

#include<iostream>
#include<unordered_map>
#include<vector>
#include<deque>
#include<algorithm>
#include<map>
#include<set>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#define int  long long

using namespace std;
const int N=550;
int map1[N][N],n,m;


void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lld",&map1[i][j]);
            map1[i][j]=map1[i][j]+map1[i-1][j];//转化为一维子序列，只需要求一维子序列的最大值
            //map1[i][j]=map1[i][j]+map1[i-1][j]+map1[i][j-1]-map1[i-1][j-1];
        }
    }
    int max1=-99999;
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int x=map1[j][1]-map1[i][1];
            max1=max(x,max1);
            for(int k=2;k<=m;k++){
                x=max(map1[j][k]-map1[i][k],x+map1[j][k]-map1[i][k]);
                max1=max(max1,x);
            }
        }
    }
    cout<<max1<<endl;
}

signed main(){
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}