Skip to content

17.24. Max Submatrix

Description

Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

Return an array [r1, c1, r2, c2], where r1, c1 are the row number and the column number of the submatrix's upper left corner respectively, and r2, c2 are the row number of and the column number of lower right corner. If there are more than one answers, return any one of them.

Note: This problem is slightly different from the original one in the book.

Example:


Input:

[

   [-1,0],

   [0,-1]

]

Output: [0,1,0,1]

Note:

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

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        s = [[0] * n for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                # ζž„ι€ εˆ—ε‰ηΌ€ε’Œ
                s[i + 1][j] = s[i][j] + matrix[i][j]

        mx = matrix[0][0]
        ans = [0, 0, 0, 0]
        for i1 in range(m):
            for i2 in range(i1, m):
                nums = [0] * n
                for j in range(n):
                    nums[j] = s[i2 + 1][j] - s[i1][j]

                start = 0
                f = nums[0]
                for j in range(1, n):
                    if f >