c++ solution with prefix-sum n' binary-search, 373ms


  • 1
    T
    class Solution {
    public:
        int lowerbound(vector<int>&vec, int val) {
            int l = 0, r = (int)vec.size();
            while (l < r) {
                int m = l + (r-l)/2;
                if (vec[m] < val) l = m+1;
                else r = m;
            }
            return l;
        }
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
            int h = matrix.size(), w = h ? matrix[0].size():0;
            if (!w) return 0;
            
            vector<vector<int>> csum(h+1, vector<int>(w+1,0));
            for (int i = 1; i <= h; ++i) {
                for (int j = 1; j <= w; ++j) {
                    csum[i][j] = csum[i][j-1]+csum[i-1][j]+matrix[i-1][j-1]-csum[i-1][j-1];
                }
            }
            int rst = INT_MIN;
            for (int i = 0; i < w; ++i) {
                for (int j = i; j < w; ++j) {
                    vector<int> rsum{0};
                    for (int l = 1; l <= h; ++l) {
                        int cur = csum[l][j+1]-csum[l][i]; // rect(0,i,l-1,j)
                        // find max(sum[m]-sum[n] <= k); i.e., find n s.t. sum[m]-k<=sum[n]
                        int indx = lowerbound(rsum, cur-k); // if n exist
                        if (indx < rsum.size()) rst = max(rst, cur-rsum[indx]); // get max sum[m]-sum[n]
                        indx = lowerbound(rsum, cur); // push sum[m]
                        rsum.insert(rsum.begin()+indx, cur);
                    }
                }
            }
            return rst;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.