classSolution{public:intmaxSumSubmatrix(vector<vector<int>>&matrix,intk){constintm=matrix.size();constintn=matrix[0].size();intans=INT_MIN;for(intbaseCol=0;baseCol<n;++baseCol){// sums[i] := sum(matrix[i][baseCol..j])vector<int>sums(m,0);for(intj=baseCol;j<n;++j){for(inti=0;i<m;++i)sums[i]+=matrix[i][j];// find the max subarray no more than kset<int>accumulate{0};intprefix=0;for(constintsum:sums){prefix+=sum;constautoit=accumulate.lower_bound(prefix-k);if(it!=cend(accumulate))ans=max(ans,prefix-*it);accumulate.insert(prefix);}}}returnans;}};
JAVA
classSolution{publicintmaxSumSubmatrix(int[][]matrix,intk){finalintm=matrix.length;finalintn=matrix[0].length;intans=Integer.MIN_VALUE;for(intbaseCol=0;baseCol<n;++baseCol){// sums[i] := sum(matrix[i][baseCol..j])int[]sums=newint[m];for(intj=baseCol;j<n;++j){for(inti=0;i<m;++i)sums[i]+=matrix[i][j];// find the max subarray no more than kTreeSet<Integer>accumulate=newTreeSet<>(Arrays.asList(0));intprefix=0;for(finalintsum:sums){prefix+=sum;finalIntegerlo=accumulate.ceiling(prefix-k);if(lo!=null)ans=Math.max(ans,prefix-lo);accumulate.add(prefix);}}}returnans;}}
Login to Codeflu
Log in to stay update and get notify on new arrivals.