max_sum.py

class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        memory = [[None for col in row] for row in matrix]
        result = float("-inf")
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                for m in xrange(i, len(matrix)):
                    for n in xrange(j, len(matrix[0])):
                        memory[m][n] = matrix[m][n]
                        if n > j:
                            memory[m][n] += memory[m][n-1]
                        if m > i:
                            memory[m][n] += memory[m-1][n]
                        if n > j and m > i:
                            memory[m][n] -= memory[m-1][n-1]
                        result = max(result, memory[m][n]) if memory[m][n] <= k else result
        return result