Max Sum of Rectangle No Larger Than K LeetCode solution in Python

1
class Solution:
2
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
3
        import numpy as np
4

5
        matrix = np.array(matrix, dtype=np.int32)
6

7
        M, N = matrix.shape
8

9
        ret = float("-inf")
10

11
        CUM = np.zeros((M, N), dtype=np.int32)
12
        for shift_r in range(M):
13
            CUM[: M - shift_r] += matrix[shift_r:]
14

15
            _CUM = np.zeros((M - shift_r, N), dtype=np.int32)
16
            for shift_c in range(N):
17
                _CUM[:, : N - shift_c] += CUM[: M - shift_r, shift_c:]
18
                tmp = _CUM[(_CUM <= k) & (_CUM > ret)]
19
                if tmp.size:
20
                    ret = tmp.max()
21
            if ret == k:
22
                return ret
23

24
        return ret