這個題目很經典的說，O（N^3）的DP。

首先偶們考察這樣的題目，簡化版：

已知一列數，求任意連續若干個數和的最大值。

SAMPLE： 3 2 -6 2 -1 7

原數3         2       -6        2       -1        7 

處理3         5       -1        2        1        8

因為是連續若干個自然數的和，那么，前面的某個數字取與不取的條件在于：以前面這個數字為結尾的連續數的和最大值是否大于0，如果大于0，那么這個數字必然要會出現在包括數字的序列中，否則無法做到最大。

所以，顯然。處理的原則是maxn[i]=max{0,maxn[i-1]}+a[i];

由于無須記錄位置。所以，可以直接用一個變量sum代替maxn數組。O(n)的掃描即可。

單列數字的問題解決了，下面我們考察多列數字的

sample:

          0     -2     -7     0 

          9      2     -6     2 

         -4      1     -4     1 

         -1      8      0    -2 



我們可以將多列數字轉換成單列數字來做！ 可以這樣設想，結果是一個長方形，我們把他壓扁，使得寬為1。

引入輔助數組st,st[i][j]代表第i列從第1行開始的數字累加到第j行的值。那么，我們每次壓扁的時候，就可以用st[i][j]-st[i][k-1]來表示第i列從第k個數字累加到第j個數字的值。達到壓縮的效果。然后用上面單列數字的方法來做。算法時間復雜度O (N^3)


我的代碼:

#include <iostream>
using namespace std;

int matrix[102][102];
int cv[102][102];
int mv[102];

int main(){
    int n;
    int lt,ll;
    
    cin>>n;
    for(lt=1;lt<=n;lt++) for(ll=1;ll<=n;ll++) cin>>matrix[lt][ll];
    for(lt=0;lt<=101;lt++) cv[lt][0]=0;
    for(lt=1;lt<=n;lt++) for(ll=1;ll<=n;ll++) cv[lt][ll]=cv[lt][ll-1]+matrix[ll][lt];
    int maxall=0,tmp,sum;
    for(lt=1;lt<=n;lt++){
        for(ll=lt;ll<=n;ll++){
            tmp=cv[1][ll]-cv[1][lt-1];
            sum=tmp;
            for(int kk=2;kk<=n;kk++){
                if(sum>0) sum+=cv[kk][ll]-cv[kk][lt-1];
                else sum=cv[kk][ll]-cv[kk][lt-1];
                if(sum>tmp) tmp=sum;
            }
            if(tmp>maxall) maxall=tmp;
        }
    }
    cout<<maxall<<endl;
    return 0;
}