最大子矩阵和的N6、N4、N3次算法

Given an NN integer matrix (aij)NN , 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. 0270 9262 92   4 1  4 1  , the maximum submatrix is   4 1 1 8 1802 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).