#DP #TableMethod #SubRectangle #UVa #Solved

108 - Maximum Sum.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=44
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int dp[110][110];
int n;

int main() {
    cin>>n;
    int x;
    for(int i= 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            cin>>x;
            dp[i][j] = dp[i][j-1] + x;
        }
    int best = 0, bestOfBest = 0 /* LOL */ , sum = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            sum = 0;
            for(int k = 1; k <= n; k++) {
                x = dp[k][j] - dp[k][j-i]; // or : x = dp[k][j] - dp[k][i-1];
                if(sum < 0) {
                    sum = x;
                } else {
                    sum += x;
                }
                if(sum > best) best = sum;
            }
            if(best > bestOfBest) bestOfBest = best;
        }
    }

    cout << bestOfBest << endl;


    return 0;
}