105-largest-sub-matrix

Largest Sub-Matrix

Challenge Description:

You have the matrix of positive and negative integers. Find a sub-matrix with the largest sum of its elements. In this case sub-matrix means a continuous rectangular part of the given matrix. There is no limitation for sub-matrix dimensions. It only has to be rectangular.

Input sample:

Your program should accept as its first argument a path to a filename. Read the matrix from this file. Example of the matrix is the following:

-1 -4 -5 -4
-5 8 -1 3
-2 1 3 2
1 5 6 -9

After some calculations you may find that the sub-matrix with the largest sum of the input is:

8 -1
1 3
5 6

Output sample:

Print out the sum of elements for the largest sub-matrix. For the given input it is:

22

Costraints:

1. Each element in the matrix is in range [-100, 100].
2. Input matrix has an equal number of rows and columns.
3. There are up to 20 rows and columns in the input file.