UVA_108_Maximum_Sum

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <stdlib.h>
#include <cmath>
#define LL unsigned long long
using namespace std;
int dp[105][105];
int main() {
    int n;
    int maxsub=-127*100*100;
    int sub;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&dp[i][j]);
            if(i>0) dp[i][j]+=dp[i-1][j];
            if(j>0) dp[i][j]+=dp[i][j-1];
            if(i>0 && j>0) dp[i][j]-=dp[i-1][j-1];
        }
    }
    for (int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=i;k<n;k++){
                for(int l=j;l<n;l++){
                  sub=dp[k][l];
                  if(i>0) sub-=dp[i-1][l];
                  if(j>0) sub-=dp[k][j-1];
                  if(i>0 && j>0) sub+=dp[i-1][j-1];
                  maxsub=max(maxsub,sub);
                }
            }
        }
    }
    printf("%d\n",maxsub);
    return 0;
}