|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importjava.util.TreeSet; |
| 4 | + |
| 5 | +/** |
| 6 | + * 363. Max Sum of Rectangle No Larger Than K |
| 7 | + * |
| 8 | + * Given a non-empty 2D matrix matrix and an integer k, |
| 9 | + * find the max sum of a rectangle in the matrix such that its sum is no larger than k. |
| 10 | +
|
| 11 | + Example: |
| 12 | + Given matrix = [ |
| 13 | + [1, 0, 1], |
| 14 | + [0, -2, 3] |
| 15 | + ] |
| 16 | + k = 2 |
| 17 | + The answer is 2. Because the sum of rectangle [[0, 1], [-2, 3]] is 2 and 2 is the max number no larger than k (k = 2). |
| 18 | +
|
| 19 | + Note: |
| 20 | + The rectangle inside the matrix must have an area > 0. |
| 21 | + What if the number of rows is much larger than the number of columns? |
| 22 | + */ |
| 23 | +publicclass_363 { |
| 24 | +/**reference: https://discuss.leetcode.com/topic/48854/java-binary-search-solution-time-complexity-min-m-n-2-max-m-n-log-max-m-n*/ |
| 25 | +publicintmaxSumSubmatrix(int[][]matrix,intk) { |
| 26 | +introw =matrix.length; |
| 27 | +if (row ==0)return0; |
| 28 | +intcol =matrix[0].length; |
| 29 | +intm =Math.min(row,col); |
| 30 | +intn =Math.max(row,col); |
| 31 | +//indicating sum up in every row or every column |
| 32 | +booleancolIsBig =col >row; |
| 33 | +intres =Integer.MIN_VALUE; |
| 34 | +for (inti =0;i <m;i++) { |
| 35 | +int[]array =newint[n]; |
| 36 | +// sum from row j to row i |
| 37 | +for (intj =i;j >=0;j--) { |
| 38 | +intval =0; |
| 39 | +TreeSet<Integer>set =newTreeSet<>(); |
| 40 | +set.add(0); |
| 41 | +//traverse every column/row and sum up |
| 42 | +for (intp =0;p <n;p++) { |
| 43 | +array[p] =array[p] + (colIsBig ?matrix[j][p] :matrix[p][j]); |
| 44 | +val =val +array[p]; |
| 45 | +//use TreeMap to binary search previous sum to get possible result |
| 46 | +Integersubres =set.ceiling(val -k); |
| 47 | +if (null !=subres) { |
| 48 | +res =Math.max(res,val -subres); |
| 49 | + } |
| 50 | +set.add(val); |
| 51 | + } |
| 52 | + } |
| 53 | + } |
| 54 | +returnres; |
| 55 | + } |
| 56 | +} |