C++, 1024ms solution.


  • 1

    First, calculate matrix sums, where sums[i][j] is the area of the square begin from (0,0) to (i,j).

    Then, in each loop iteration, consider all the squares with column boundary cl and cr. (If the column size is greater, we will consider all the square with the same row boundaries)

    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        if (matrix.empty()||matrix[0].empty()) return 0;
        int rsz=matrix.size(),csz=matrix[0].size();
        if (matrix[0][0]==k) return k;
        vector<vector<int>> sums=matrix;
        int maxSum=INT_MIN;
        int temp;
        for (int i=1;i<rsz;i++){
            sums[i][0]+=sums[i-1][0];
        }
        for (int j=1;j<csz;j++){
            sums[0][j]+=sums[0][j-1];
        }
        for (int i=1;i<rsz;i++)
        for (int j=1;j<csz;j++){
            sums[i][j]+=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1];
        }
        
        for (int cl=0;cl<csz;cl++){
            for (int cr=cl;cr<csz;cr++){
                set<int> area;
                set<int>::iterator iter;
                int curArea;
                area.insert(0);
                for (int rd=0;rd<rsz;rd++){
                    curArea=sums[rd][cr]-(cl==0?0:sums[rd][cl-1]);
                    iter=area.lower_bound(curArea-k);
                    if (iter!=area.end()){
                        maxSum = max(maxSum,curArea-(*iter));
                        if (maxSum==k) return k;
                    }
                    area.insert(curArea);
                }
            }
        }
        return maxSum;  
    }

Log in to reply
 

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