Участник:Novitskiy97/Max Sum of Rectangle No Larger than K

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/

Python 3

 
import bisect
 
class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], target: int) -> int:
        row = len(matrix)
        col = len(matrix[0])
        res = -2 ** 31
 
        for i in range(col):
            col_sum = [0 for k in range(row)]
            for j in range(i, col):
                for k in range(row):
                    col_sum[k] += matrix[k][j]
 
                temp = [0]
                cur_sum = 0
 
                for k in range(row):
                    cur_sum += col_sum[k]
                    temp_target = cur_sum - target
                    idx = bisect.bisect_left(temp, temp_target)
                    if idx != len(temp):
                        res = max(res, cur_sum - temp[idx])
                    bisect.insort_left(temp, cur_sum)
        return res