# 363. Max Sum of Rectangle No Larger Than K

二维矩阵中最大和不超过K的长方形，它的和是多少。这道题如果把不超过K的限制去了，本身也是个hard题，在此基础上要求找和不大于K的最大和，难上加难。先不看K的限制，一维最大子数组用常见subarray DP套路，即分别看以i结尾子数组最大和会是多少。二维矩阵以列为基准，固定l，r不断++，维持一个长度为N的数组sum，sum\_i表示第i行从l累加到r是多少， 再对sum数组求最大子数组。此时得到就是以l和r为两边，最大子长方形是多少，如图所示:

![](https://pic2.zhimg.com/80/v2-ed9d241b6a3abdab053c4b2679ac7399_hd.jpg)

然后我们遍历所有可能的l和r得出global最优。对于这道题还要把对sum求max sum subarray替换成求对sum找不大于K的最大子数组和: 把presum思想中用于找sum中有没有何为K的子数组的hash set替换成tree set使得所有sum元素有序，也就能找最接近K的子数组了。

解法参考自[这](https://link.zhihu.com/?target=https%3A//www.cnblogs.com/grandyang/p/5617660.html)。

```cpp
/*
 * @lc app=leetcode id=363 lang=cpp
 *
 * [363] Max Sum of Rectangle No Larger Than K
 *
 * https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/description/
 *
 * algorithms
 * Hard (35.57%)
 * Likes:    487
 * Dislikes: 36
 * Total Accepted:    30.4K
 * Total Submissions: 85.3K
 * Testcase Example:  '[[1,0,1],[0,-2,3]]\n2'
 *
 * 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:
 * 
 * 
 * Input: matrix = [[1,0,1],[0,-2,3]], k = 2
 * Output: 2 
 * Explanation: 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?
 * 
 */

// @lc code=start
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
         const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
         vector<vector<int>> sum(M, vector<int>(N, 0));
         int res = INT_MIN;
         for (int i = 0; i < N; ++i) {
             vector<int> sum(M);
             for (int j = i; j < N; ++j) {
                 for (int k = 0; k < M; ++k) {
                     sum[k] += matrix[k][j];
                 }
                 int cur_sum = 0;
                 set<int> s({0});
                 for (auto a : sum) {
                     cur_sum += a;
                     const auto it = s.lower_bound(cur_sum - k);
                     if (it != s.end()) res = max(res, cur_sum - *it);
                     s.insert(cur_sum);
                 }
             }
         }
         return res;
    }
};
// @lc code=end


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/subarray-sum/363.-max-sum-of-rectangle-no-larger-than-k.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.