Given a M × M array of positive and negative integers, find the sub-rectangle with the largest sum. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. The input to the program is the value of M followed by the array itself.
Input:
First line contains M ( 1 <= M<= 100 )
Next M lines contains M elements each, describing the matrix A ( -100 <= A[i][j] <= 100 )
Output:
The Maximum Sum (Followed by a '\n' which is just for a newline, no need to display)
Sample Cases:
Input:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
Output:
15
how to solve this one!!!