- 32.5%

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

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.

1 | Example: |

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?

https://discuss.leetcode.com/topic/48875/accepted-c-codes-with-explanation-and-references

Accepted C++ codes with explanation and references

The naive solution is brute-force, which is O((mn)^2). In order to be more efficient, I tried something similar to Kadane’s algorithm. The only difference is that here we have upper bound restriction K. Here’s the easily understanding video link for the problem “find the max sum rectangle in 2D array”: Maximum Sum Rectangular Submatrix in Matrix dynamic programming/2D kadane (Trust me, it’s really easy and straightforward).

Once you are clear how to solve the above problem, the next step is to find the max sum no more than K in an array. This can be done within O(nlogn), and you can refer to this article: max subarray sum no more than k.

For the solution below, I assume that the number of rows is larger than the number of columns. Thus in general time complexity is O[min(m,n)^2 * max(m,n) * log(max(m,n))], space O(max(m, n)).

1 | int maxSumSubmatrix(vector<vector<int>>& matrix, int k) { |

https://discuss.leetcode.com/topic/49781/no-real-dp-technique-actually-used-c-critically-commented

No real DP technique actually used C++, critically commented

The last section of the solution can be tricky, but read it carefully and I believe you can get it done!

Good luck!

1 | class Solution { |

https://discuss.leetcode.com/topic/48930/any-accepted-python-solution

Any Accepted Python Solution?

I got a TLE for the Python code below, because the time cost of bisect.insort is O(n) for a built-in list.

The code was rejudged as accepted just now, but very slow… 1800ms+

1 | class Solution(object): |

Could anybody share a more efficient Python solution? Thank you :D