最大子陣和

最大子陣和

hoj2558，給定一個矩陣，返回最大的子矩陣的和。

思路（動態規劃）：

1.讀入矩陣的同時計算部分和矩陣

2.枚舉矩陣的行上下邊界，固定了行上下邊界後，

根據部分和矩陣在O(1)時間內得到同一列元素的和，轉化為1維數組的情況

3.按照一維數組的情況，求最大子數組和的思路是：

可以從後往前計算，每次先算以當前元素A[i]為開頭的最大和start，

再將start與當前A[i+1:n]所代表的真實最大和進行比較，作為A[i:n]的真實最大和保存起來。

4.輸出遍歷過程中得到的最大值MAX即可

cpp代碼：

#include
#define SIZE 102
#define INF 1000
using namespace std;
int maxx(int a,int b){
    return a>b?a:b;
}
int main(){
    int n,i,j,k,a,c,tmp,MAX,start,all;
    int num[SIZE];
    int mat[SIZE][SIZE];
    while(cin>>n){
        //讀入矩陣的同時計算部分和矩陣
        for(j=0;j<=n;j++)mat[0][j]=mat[j][0]=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                cin>>mat[i][j];
                mat[i][j]+=mat[i-1][j];//累積部分和
            }
        }
        //開始處理
        MAX=-INF;
        for(a=1;a<=n;a++){
            for(c=a;c<=n;c++){//枚舉上下邊界
                start=mat[c][n]-mat[a-1][n];
                all=start;//先給數組最後一個元素賦值
                for(k=n-1;k>=1;k--){//從後往前計算
                    tmp=mat[c][k]-mat[a-1][k];//根據部分和算出當前元素值
                    start=maxx(tmp+start,tmp);//先比較以tmp開頭的
                    all=maxx(start,all);//再比較總的
                }
                if(all>MAX)MAX=all;
            }
        }
        cout<