Description. An informal, intuitive description of your dynamic programming algorithm. This description should indicate the choice(s) your algorithm is making.

Algorithm. A formal statement of your algorithm written using the codebox environment.

Correctness. An argument that your algorithm is correct.

Running Time. A statement of the running time of your algorithm and an argument that your algorithm runs in the stated time.

Suppose we have an n-by-n matrix M[1..n, 1..n]. A submatrix of M is a subarray M[i..j, k..l] for some indices i j and k l. The sum of a submatrix is the sum of all elements in that submatrix.

Input: An n-by-n matrix M[1..n, 1..n] of integers (positive and negative).

Output: The maximum sum of any submatrix in M.

Hint: Think about this problem in one dimension first, that is, think about finding the maximum sum of any subarray A[i..j] in an array A.