Max Sum of Rectangle No Larger Than K

Problem: Max Sum of Rectangle No Larger Than K

We can first try all left-col and right-col compositions. For each compositions, we can get sum of each row and get an array by this way, which means we can downgrade this problem to a maximum subarray less than k problem.

For this kind of problem, we need find maximum sumA - sumB < k. Suppose we already have an array of sorted sums. In this array, sumB' < sumB < sumB''. Here comes sumA. We know that sumA - sumB > sumA - sumB''. So what we are finding now is sumA - sumB'' < sumA - sumB < k <= sumA - sumB', which means we need to find sumB' < sumA-k< sumB < sumB''.

Code in Python:

import bisect

class Solution(object):
    def maxSumSubmatrix(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        def maxSubArrayLessK(nums, k):
            cumset=[]
            cumset.append(0)
            maxsum=-1<<32
            cursum=0
            for i in xrange(len(nums)):
                cursum+=nums[i]
                # find the lower bound of the index
                idx=bisect.bisect_left(cumset,cursum-k)
                # find max in sum[right]-sum[left]<=k
                if 0<=idx<len(cumset):
                    maxsum=max(maxsum,cursum-cumset[idx])
                # using insort instead of append since bisect_left reason
                bisect.insort(cumset,cursum)
            return maxsum


        if not matrix or not matrix[0]:
            return 0
        row,col=len(matrix),len(matrix[0])
        res=-(1<<32)
        # using two pointer to record the scan position
        for left in xrange(col):
            # reset mem to store the row data
            cursums=[0 for _ in xrange(row)]
            # since the rectange has area>0 
            right=left
            while right<col:
                # count one row
                for i in xrange(row):
                    cursums[i]+=matrix[i][right]
                # find the max in this row
                curarrmax=maxSubArrayLessK(cursums,k)
                res=max(res,curarrmax)
                right+=1

        return res