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:

Given matrix = [

  [1,  0, 1],

  [0, -2, 3]

]

k = 2

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:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

思路：

　　使用l和r划定长方形的左右边界范围，然后在这个范围内，依次记录长方形的上界固定为第一行，下界从第一行到最后一行对应的长方形的和到数组sum。现在问题转换为寻找最合适的sum[j]-sum[i](j和i对应长方形的上下界)，使得该值不大于k，但是最接近k。这个问题可以从Quora上找到解答：

　　You can do this in O(nlog(n))

　　First thing to note is that sum of subarray (i,j] is just the sum of the first j elements less the sum of the first i elements. Store these cumulative sums in the array cum. Then the problem reduces to finding  i,j such that i<j and cum[j]−cum[i] is as close to k but lower than it.

　　To solve this, scan from left to right. Put the cum[i] values that you have encountered till now into a set. When you are processing cum[j] what you need to retrieve from the set is the smallest number in the set such which is not smaller than cum[j]−k. This lookup can be done in O(log(n)) using lower_bound. Hence the overall complexity is O(nlog⁡(n)).

　　Here is a c++ function that does the job, assuming that K>0 and that the empty interval with sum zero is a valid answer. The code can be tweaked easily to take care of more general cases and to return the interval itself.

　　对应代码：

int best_cumulative_sum(int ar[],int N,int K)

{

    set<int> cumset;

    cumset.insert();

    int best=,cum=;

    for(int i=;i<N;i++)

    {

        cum+=ar[i];

        set<int>::iterator sit=cumset.lower_bound(cum-K);

        if(sit!=cumset.end())best=max(best,cum-*sit);

        cumset.insert(cum);

    }

    return best;

}

　　在上述基础之上，我们稍加改变，就能够写出下述代码完成此题了。

class Solution {

public:

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

        int row = matrix.size();

        if (row == )

            return ;

        int col = matrix[].size();

        int ret = INT_MIN;

        for (int l = ; l < col; l++) {

            vector<int> sums(row, );

            for (int r = l; r < col; r++) {

                for (int i = ; i < row; i++)

                    sums[i] += matrix[i][r];

                // Find the max subarray no more than K

                set<int> sumSet;

                sumSet.insert();

                int curSum = ;

                int curMax = INT_MIN;

                for (auto sum:sums) {

                    curSum += sum;

                    auto it = sumSet.lower_bound(curSum - k);

                    if (it != sumSet.end())

                        curMax = max(curMax, curSum - *it);

                    sumSet.insert(curSum);

                }

                ret = max(ret, curMax);

            }

        }

        return ret;

    }

};