C++, 536ms Binary Search solution


  • 0

    The insert() of vector is pretty fast, so it is OK to use vector and binary search.
    Otherwise, we can use binary search tree. The algorithm is the same. Just keep the visited value sorted on the air.

    class Solution {
    public:
    int bs(vector<int> &nums, int n){
        if (nums.empty()) return 0;
        if (n>nums.back()) return nums.size();
        int l=0,r=nums.size()-1,mid;
        while (l<r){
            mid = l+(r-l)/2;
            if (nums[mid]<n){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l;
    }
    
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        if (matrix.empty() || matrix[0].empty()) return -1;
        int rsz=matrix.size(),csz=matrix[0].size();
        vector<vector<int>> ltSum(rsz+1,vector<int>(csz+1,0));
        for (int i=0;i<rsz;i++){
            for (int j=0;j<csz;j++){
                ltSum[i+1][j+1] = ltSum[i+1][j]+ltSum[i][j+1]-ltSum[i][j]+matrix[i][j];
            }
        }
        int res=INT_MIN;
        for (int i=0;i<csz;i++){
            for (int j=i;j<csz;j++){
                vector<int> temp;
                temp.push_back(0);
                for (int l=1;l<=rsz;l++){
                    int curSum = ltSum[l][j+1]-ltSum[l][i];
                    int idx = bs(temp,curSum-k);
                    if (idx<temp.size()){
                        res = max(res,curSum-temp[idx]);
                    }
                    idx = bs(temp,curSum);
                    temp.insert(temp.begin()+idx,curSum);
                }
            }
        }
        return res;
    }
    };

Log in to reply
 

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