A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3SAT) is NPcomplete. The problem 2SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.
Given a 2dimensional array of positive and negative integers, find the subrectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the subrectangle with the largest sum is referred to as the maximal subrectangle. A subrectangle is any contiguous subarray of size 1 x 1 or greater located within the whole array. As an example, the maximal subrectangle of the array:
0 2 7 0
9 2 6 2
4 1 4 1
1 8 0 2
is in the lowerlefthand corner:
9 2
4 1
1 8
and has the sum of 15.
The input consists of an N x N array of integers. 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 N^2 integers separated by whitespace (newlines and spaces). These N^2 integers make up the array in rowmajor order (i.e., all numbers on the first row, lefttoright, then all numbers on the second row, lefttoright, etc.). N may be as large as 100. The numbers in the array will be in the range [127, 127].
The output is the sum of the maximal subrectangle.
4
0 2 7 0 9 2 6 2
4 1 4 1 1
8 0 2
15
This challenge is provided by the ACM International Collegiate Programming Contest.
Please log in to submit your solution.
Difficulty 

Average test runtime  0.33 
Points (changes over time)  10 
Tried by  8 users 
Solved by  5 users 
#  Name  Runtime  Points worth 

1  Chris Danger  0.17  14 
2  Justin  0.17  14 
3  ,s/java/NaN/gi  0.17  14 
4  Nis  0.56  4 
5  Skøgland  0.60  4 