Given an NN integer matrix (aij)NN , find the maximum value of a
1 i m N and 1 j n N . For convenience, the maximum submatrix sum is 0 if all the integers are negative.
Example: For matrix and has the sum of 15.
0270 9262
92
4 1 4 1 , the maximum submatrix is
4 1 1 8
1802
The simplest method is to compute every possible submatrix sum and find the
maximum number. An algorithm similar to Algorithm 1 given in Section 2.4.3 will runin O(N6),andtheonesimilartoAlgorithm2in O(N4).
1