363. Max Sum of Rectangle No Larger Than K

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

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

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

解法参考自这。

/*
 * @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