Maximum Submatrix

LintCode 944

Given an n x nmatrix of positiveand negativeintegers, find the submatrix with the largest possible sum.

Example

Given matrix = 
[
[1,3,-1],
[2,3,-2],
[-1,-2,-3]
]
return 9.
Explanation:
the submatrix with the largest possible sum is:
[
[1,2],
[2,3]
]

这题和上一题 submatrix sum 的套路一摸一样。这里就写一个 2D kadane 的做法，因为程序较短

具体思路见上一题

    def maxSubmatrix(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        m, n = len(matrix), len(matrix[0])
        best = matrix[0][0]

        for lo in xrange(m):
            for hi in xrange(lo, m):
                if lo == hi:
                    oneD = matrix[lo]
                else:
                    oneD = map(sum, zip(oneD, matrix[hi]))

                currentMax = oneD[0]             #完全按一维数组来做
                best = max(best, currentMax)
                for n in oneD[1:]:
                    currentMax = max(n, currentMax + n)
                    best = max(best, currentMax)

        return best