Max Sum of Rectangle No Larger Than K -- LeetCode

[Question]

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).

[Analysis]

Using brute force, every rectangle needs to be checked. For a matrix m x n, the time complexity is O(m^2 x n^2).

Consider the one-dimensional array, A[0], A[1] ... A[n-1], to get a max sum of a consecutive sub-array is no larger than K, we can construct the cumulative sum array: S[0] = A[0], S[1]=S[0]+A[1], ... S[i]=S[i-1]+A[i], ..S[n-1]=S[n-2]+A[n-1]. Sum of A's sub-array A[i]..A[j] = S[j]-S[i-1]. The problem becomes, for a given S[j], apply binary search on S[0],...S[j-1], to find S[j]-K. 

On two-dimensional matrix, we can construct this kind of one-dimensional array array between any two columns. Then we can find the needed rectangle in time complexity O( m x n^2 x log n).

[Solution]

class Solution {

public:

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

        int m=matrix.size(), n=matrix[0].size();

        int res=INT_MIN;

        for (int i=0; i<n; i++)  {

            vector<int> list(m, 0);

            for (int j=i; j<n; j++) {

                for(int k=0; k<m; k++) {

                    list[k]+=matrix[k][j];

                }

                set<int> sums;

                sums.insert(0);

                int curSum = 0;

                for(auto a: list) {

                    curSum+=a;

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

                    if (it!=sums.end()) res = max(res, curSum-*it);

                    sums.insert(curSum);

                }

            }

        }

        return res;

    }

};