You are Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. The sub-rectangle with the largest sum is referred to as the Best sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array:
0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
9 2 -4 1 -1 8
which is in the lower-left-hand corner, and has the sum of 15.
The input consists of several test cases. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by Integer values for the square. These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [-127, 127]. Terminate the input with N=0.
The output is the sum of the maximal sub-rectangle.
Input: 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 0 Output: 15
|Time Limit:||0.78481 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, SQL, TEXT|
Fetching successful submissions