卖萌的弱渣

I am stupid, I am hungry.

Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

1
2
3
4
5

Given matrix = [
  [1,  0, 1],
  [0, -2, 3]
]
k = 2

The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2).

Note:

The rectangle inside the matrix must have an area > 0. What if the number of rows is much larger than the number of columns?

Solution

(Max-Sum-of-Rectangle-No-Larger-Than-K.py) download
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
30
31
32

class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """

        m = len(matrix)
        n = len(matrix[0]) if m else 0

        # 并不知道行和列哪个大
        M = max(m,n)
        N = min(m,n)

        ans = None
        for x in range(N):
            sums = [0]*M
            for y in range(x,N):
                # num 为[x->N, 0->M]这个矩阵中的和
                slist, num = [], 0
                for z in range(M):
                    # 不知道行和列哪个大
                    sums[z] += matrix[z][y] if m>n else matrix[y][z]
                    num += sums[z]
                    if num <=k:
                        ans = max(ans,num)
                    i = bisect.bisect_left(slist, num-k)
                    if i != len(slist):
                        ans = max(ans, num-slist[i])
                    bisect.insort(slist,num)
        return ans or 0