zoj 1074 to the max（dp+最大子矩阵）

#include <algorithm>
#include <cstring>
using namespace std;
int n,dp[120],maxsum,ans,mat[120][120],sum[120][120];
int (int up,int below){
    maxsum=0;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        dp[i]=max(dp[i-1]+sum[i][below]-sum[i-1][below]-sum[i][up-1]+sum[i-1][up-1],sum[i][below]-sum[i-1][below]-sum[i][up-1]+sum[i-1][up-1]);
        maxsum=max(maxsum,dp[i]);
    }
    return maxsum;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            scanf("%d",&mat[i][j]),sum[i][j]=mat[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            ans=max(ans,query(i,j));
        }
    }
    printf("%dn",ans);
    return 0;
}