王道机试指南 例题12.3 最大子矩阵

题目：

算法及思路：

代码：

#include <iostream>
#include <ostream>
#include <algorithm>
using namespace std;

int MaxSeqSum(int* a,int n){//动态规划求一维数组的最大子序列和
    int dpi[n];
    for(int i=0;i<n;i++){
        if(i==0) dpi[i]=a[i];
        else{
            dpi[i]=max(dpi[i-1]+a[i],a[i]);
        }
    }
    sort(dpi,dpi+n);
    return dpi[n-1];
}

int main() {
    int n;
    while(cin>>n){
        int a[n][n];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>a[i][j];

        int max=0;

        for(int s=0;s<n;s++){//遍历所有从s行到e行的情况
            for(int e=s;e<n;e++){
                int rowSum[n];
                for(int l=0;l<n;l++)
                    rowSum[l]=0;
                for(int j=0;j<n;j++)//从s行到e行的每列元素累加形成一维的rowSum
                    for(int i=s;i<=e;i++)
                        rowSum[j]+=a[i][j];

                int t= MaxSeqSum(rowSum,n);//求一维数组的最大子序列和
                if(t>max) max=t;//记录最大值
            }

        }
        cout<<max<<endl;
    }
    return 0;
}

运行结果：