C++ 46ms solution,beats 99.78%


  • 3
    Z

    class Solution {
    public:

    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int m=matrix.size();
        if(m==0) return 0;
        int n=matrix[0].size();
        int res=INT_MIN;
        for(int i=0;i<n;i++) {  // the number of columns is smaller
            vector<int> sums(m,0);
            for(int j=i;j<n;j++) {
                for(int row=0;row<m;row++) {
                    sums[row]+=matrix[row][j];
                }
                int ms = maxSumArray(sums, k);
                if (ms == k) return ms;
                if (ms < k && ms > res) res = ms;
          
            }
        }
        return res;
    }
     
    int maxSumArray(vector<int> & arr, int k) {
        int sum = 0, maxS = INT_MIN;
        for (int i = 0; i < arr.size(); i++) {  //it's a trick. Maybe O(n) to solve this problem
            sum += arr[i];
            maxS = max(sum, maxS);
            if (sum == k ) return sum;
            if (sum < 0) sum = 0;
        }
        if (maxS <= k) return maxS;
        maxS= INT_MIN;
        set<int>sums;
        sum = 0;
        sums.insert(0);
        for (int i = 0; i < arr.size(); i++) {
            sum += arr[i];
            auto it = sums.lower_bound(sum - k);
            if (it != sums.end()) maxS = max(sum - *it, maxS);
            sums.insert(sum);
        }
        return maxS;
    }  
    

    };


  • 0
    T

    Nice idea to calculate the max subsequence sum first !


  • 0
    B

    wonderful idea! Just calculating the max sum firstly


  • 0
    V

    There is no need to insert element 0 for temp Sums.


Log in to reply
 

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