#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector <vector <int>> a(n, vector <int> (n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    int ans = a[0][0];
    for (int leng = 1; leng <= n; leng++){
        for (int up = 0; up <= n-leng; up++){
            vector <long long> sumv(n);
            for (int j = 0; j < n; j++) {
                for (int i = up; i < up + leng; i++) {
                    sumv[j] += a[i][j];
                }
            }
            int sum = 0;
            for (int r = 0; r < n; ++r) {
                sum += sumv[r];
                ans = max(ans, sum);
                sum = max(sum, 0);
            }
        }
    }
    cout << ans;
}

My code is as following:
#include<iostream>
#include<vector>
using namespace std;

long getMaxSumRow(long rowArr[], int n) {
    long cs = 0;
    long ms = 0;
    bool positiveNumberPresent = false;

    for (int i = 0; i < n; i++) {
        if (!positiveNumberPresent && (rowArr[i] >= 0)) {
            positiveNumberPresent = true;
        }
        cs += rowArr[i];

        if (cs < 0) {
            cs = 0;
            continue;
        }

        if (cs > ms) {
            ms = cs;
        }
    }

    if (positiveNumberPresent) {
        return ms;
    }

    ms = rowArr[0];

    for (int i = 0; i < n; i++) {
        if (rowArr[i] > ms) {
            ms = rowArr[i];
        }
    }

    return ms;
}

long maxSumRec(vector<vector<long> > &arr, int n) {
    if (n == 1) {
        return arr[0][0];
    }

    /* Take an array for running rows sum */
    long runningRowSum[n];

    for (int r = 0; r < n; r++) {
        runningRowSum[r] = 0;
    }

    long maxSum = INT_MIN;

    /* Initialize variables for left-right and top-bottom bounds */
    int left, right, top = 0, bottom = n-1;

    /* Iterate from all possible lefts to all possibe rights ahead of this left */
    for (left = 0; left < n; left++) {
        for (right = 0; right < n; right++) {
            for (top = 0; top <= bottom; top++) {
                runningRowSum[top] += arr[top][right];
            }
            /* For this left-right combination, calculate contigeous subarray with maximum sum in runningRowSum */
            long currSum = getMaxSumRow(runningRowSum, n);

            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        /* Reinitialize running row sum to 0 */
        for (int r = 0; r < n; r++) {
            runningRowSum[r] = 0;
        }
    }

    return maxSum;
}

int main() {
    int n;
    cin >> n;
    vector<vector<long> > arr(n);

    for (int i = 0; i < n; i++) {
        arr[i] = vector<long>(n);
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    cout << maxSumRec(arr, n);
    return 0;
}

But I am getting wrong answer for test case#3 . Any advice on what it might be failing at ?

I can't understand how to solve the problem with Python and meet time limitations. I implemented solution with creating 3-D list of subsumes[column][row_start][row_offset] using accumulate from itertools and list comprehension.

After that I used Kadane's algorithm. I expect that it works with O(N^3). But it isn't enough...

Are there some tricks in the problem for Python? Except for stdin of course.

Please, give me some tests!

Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce?

Edited by author 25.07.2017 20:10

My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason?

#include <iostream>
using namespace std;

const int M = 107;

int mat[M][M][M][M];

int main() {
    int n;
    cin >> n;
    int arr[n][n];

    int ans = -1e9;

    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) {
            cin >> arr[i][j];
            mat[i][j][i][j] = arr[i][j];
            if (arr[i][j] > ans) ans = arr[i][j];
        }


    for (int size = 2; size<=n*n; size++) {
        for (int p=1; p<=size and p<=n; p++) {
            int q =  size/p;
            if (p*q != size) continue;


            for (int i=0; i<n-p+1; i++) {
                for (int j=0; j<n-q+1; j++) {

                    int x1 = i,     y1 = j;
                    int x2 = i+p-1, y2 = j+q-1;

                    if (x2-x1 > y2-y1) {
                        mat[x1][y1][x2][y2] = mat[x1][y1][x2-1][y2] + mat[x2][y1][x2][y2];
                        if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2];
                    }
                    else {
                        mat[x1][y1][x2][y2] = mat[x1][y1][x2][y2-1] + mat[x1][y2][x2][y2];
                        if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2];
                    }

                }
            }



        }
    }

    cout << ans << endl;

}

Edited by author 26.06.2017 17:06

Edited by author 26.06.2017 17:06

Edited by author 26.06.2017 17:07

There a[i][j] in [-127..127]  and  n <= 100 -- May be there bitmask tricks, or other tricks????

#include <iostream>
using namespace std;
int n,A[1002],i,maxi,S[1002],st,dr,rez;
int main()
{   cin>>n;
    for(i=1;i<=n;i++)
        cin>>A[i];
    S[1]=A[1];
    for(i=1;i<=n;i++)
        if(S[i-1]<=0)
            S[i]=A[i];
        else
            S[i]=A[i]+S[i-1];
    rez=-1000000;
    for(i=1;i<=n;i++)
        if(S[i]>rez)
            rez=S[i];
    cout<<rez;
    return 0;
}

please help me if you have O(n^2) algorithm for this problem .
thanks

oh i found my mistake


Edited by author 03.11.2014 12:28

Firstly my solution got TLE#4. Next, I make mew solution with new idea, and got WA#4.
Also, my 2nd solution makes mistake in this test:

4
0 -2 -1 0
9 2 -9 -2
-4 1 -1 1
-1 8 10 -2

answer is 18.

It can help someone.
P.S. forry for bad English.

I haven't idea how to approach this test?
my code is simple O(n^4),but #9 test doesn' work:

for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)

            s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];



    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        {
            for (k=i;k<=n;k++)
            {
                for (m=j;m<=n;m++)
                {
                    sum=s[k][m]-s[i-1][m]-s[k][j-1]+s[i-1][j-1];

                    if (sum>max1) max1=sum;

                }
            }
        }

I was little discouraged when my O(n^4) solution got AC.What remains the purpose of Dp ,if I could do it by complete search.

Please mail me the O(n^3),O(n^2),O(n) solution for this task,any or all complexity written here.
My mail id is royalbird.raman@gmail.com
thanks for your support

Please can anybody tell me what is test case #11

I get WA in Test#3..can anybody give me some test please?
all test that i found passed right..
thanks!

My program gets WA #5. Did anybody have the same problem? Program works correctly with all inputs I have found.

Edited by author 09.09.2012 13:01

Gimme some tests, please :) All tests that I found my program passed right, I can't understand my mistake.
Now I have WA4 :)


Edited by author 08.07.2012 10:07

try this:

sample input:
2
-1 -2
-3 -4

sample output:
-1