[Help!] Why my naive dp solution got TLE (:


  • 0
    J
    class Solution(object):
        def maxSumSubmatrix(self, matrix, k):
            """
            :type matrix: List[List[int]]
            :type k: int
            :rtype: int
            """
            if not matrix or not matrix[0]:
                return 0
            
            n, m = len(matrix), len(matrix[0])
            dp = [[0 for j in xrange(m + 1)] for i in xrange(n + 1)]
            for i in xrange(1, n + 1):
                for j in xrange(1, m + 1):
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + matrix[i - 1][j -1]
            
            res = float('-inf')    
    
            for row1 in xrange(1, n + 1):
                for row2 in xrange(row1, n + 1):
                    for col1 in xrange(1, m + 1):
                        for col2 in xrange(col1, m + 1):
                            temp_sum = dp[row2][col2] - dp[row2][col1 - 1] - dp[row1 - 1][col2] + dp[row1 - 1][col1 - 1]
                            if temp_sum < k:
                                res = max(res, temp_sum)
                            elif temp_sum == k:
                                return k
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.