UVA 108 - Maximum Sum (2D MAX SUM)

UVA 108 - Maximum Sum (2D MAX SUM) 

Problem: Given 2D (N*N) array with some +ve & -ve integers. 

You have to compute the sum of submatrix with maximum sum.

IDEA:
   1.) Fix one column lft .
   2.) Fix one column rgt from lft to rgtmost corner.
   3.) For every fixed lft & rgt column, traverse below rowwise &

        calculate cumulative sum.
        Note: We have to precalculate rowise sum earlier.
   4.) If sum becomes negative then, make it 0 & update maximum sum on every step.
So, overall complexity is O(N^3). 

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;

///  dp10it    0123456789012345678 ///
#define MX     102
#define inf    1000000010
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int n,dp[MX][MX];
int main() {
    int tc,cs=1,i,j,k,x;
    S(n);
    fr(i,1,n){
        fr(j,1,n){
            S(x);
            dp[i][j]=dp[i][j-1]+x;
        }
    }
    int mx=-inf;
    for(i=1;i<=n;i++){ ///First column;
        for(j=i;j<=n;j++){ ///Second column
            int mxx=-inf,sm=0;
            for(k=1;k<=n;k++){
                x=dp[k][j]-dp[k][i-1];
                sm+=x;
                mxx=max(mxx,sm);
                if(sm<0)sm=0;
            }
            mx=max(mx,mxx);
        }
    }
    printf("%lld\n",mx);

    return 0;
}