题解 | #最大子序列#

二维最大子序列解法： 1.划归为一维最大子序列解法，即i-j行的矩阵转化为i-j行各列元素累加后形成的子序列一维解 2.注意一维子序列最大子序列和的解是dp数组元素的最大值，dp[i]表示的是以i为结尾的最大子序列和

#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int maxSequence(int t[],int n){
    int r[n];
    for(int i=0;i<n;i++){
        if(i>0){
            r[i] = max(t[i]+r[i-1], t[i]);
        }else{
            r[i] = t[i];
        }
    }
    return *max_element(r,r+n);
}
int main(){
    int k = 0;
    while(cin>>k){
        int t[k][k]; 
        for(int i=0;i<k;i++){
            for(int j=0;j<k;j++){
                cin>>t[i][j];
            }
        }
        int total[k][k];
        for(int i=0;i<k;i++){
            for(int j=0;j<k;j++){
                if(i==0){
                    total[i][j] = t[i][j];
                }else{
                    total[i][j] = t[i][j] + total[i-1][j];
                }
            }
        }
        int maxR = 0x80000000;
        int arr[k];
        for(int i=0;i<k;i++){
            for(int j=i;j<k;j++){
                for(int x=0;x<k;x++){
                    if(i==0){arr[x] = total[j][x];}
                    else{arr[x]=total[j][x]-total[i-1][x];}
                    
                }
                maxR = max(maxR,maxSequence(arr,k));
            }
        }
        cout<<maxR<<"\n";
    }
    
}