面试题 17.24. 最大子矩阵

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例：

输入：
[
  [-1,0],
  [0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵

说明：

• 1 <= matrix.length, matrix[0].length <= 200

Python 解答：
1.动态规划

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        dp = [[0 for i in range(len(matrix[0]))]for j in range(len(matrix)+1)]
        for i in range(1, len(matrix)+1):
            for j in range(len(matrix[0])):
                dp[i][j] += matrix[i-1][j]+dp[i-1][j]
        max_total = matrix[0][0]
        max_i, max_j, max_l, max_r = 0, 0, 0, 0
        for i in range(len(matrix)):
            for j in range(i+1, len(matrix)+1):
                total = dp[j][0]-dp[i][0]
                begin = 0
                k = 1
                while k < len(matrix[0]):
                    temp = dp[j][k]-dp[i][k]
                    if total < 0:
                        total = temp
                        begin = k
                    else:
                        total += temp
                    if total > max_total:
                        max_i = i 
                        max_j = j-1
                        max_l = begin
                        max_r = k
                        max_total = total
                    k += 1
        return [max_i, max_l, max_j, max_r]