package com.fishercoder.solutions;

import java.util.TreeSet;

/**
 * 363. Max Sum of Rectangle No Larger Than K
 *
 * Given a non-empty 2D matrix matrix and an integer k,
 * find the max sum of a rectangle in the matrix such that its sum is no larger than k.

 Example:
 Given matrix = [
 [1,  0, 1],
 [0, -2, 3]
 ]
 k = 2
 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).

 Note:
 The rectangle inside the matrix must have an area > 0.
 What if the number of rows is much larger than the number of columns?
 */
public class _363 {
    /**reference: https://discuss.leetcode.com/topic/48854/java-binary-search-solution-time-complexity-min-m-n-2-max-m-n-log-max-m-n*/
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;
        int m = Math.min(row, col);
        int n = Math.max(row, col);
        //indicating sum up in every row or every column
        boolean colIsBig = col > row;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            int[] array = new int[n];
            // sum from row j to row i
            for (int j = i; j >= 0; j--) {
                int val = 0;
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                //traverse every column/row and sum up
                for (int p = 0; p < n; p++) {
                    array[p] = array[p] + (colIsBig ? matrix[j][p] : matrix[p][j]);
                    val = val + array[p];
                    //use  TreeMap to binary search previous sum to get possible result
                    Integer subres = set.ceiling(val - k);
                    if (null != subres) {
                        res = Math.max(res, val - subres);
                    }
                    set.add(val);
                }
            }
        }
        return res;
    }
}

@@ -600,15 +600,56 @@
 3 %7B%0A
+    public static class Solution1 %7B%0A    
     /**
+ 
 refe
@@ -773,15 +773,20 @@
 -m-n
+ 
 */%0A    
+   
+ 
 publ
@@ -837,24 +837,28 @@
 ) %7B%0A        
+    
 int row = ma
@@ -874,24 +874,28 @@
 th;%0A        
+ 
+   
 if (row == 0
@@ -906,24 +906,28 @@
             
+   
+ 
 return 0;%0A  
@@ -924,34 +924,42 @@
 turn 0;%0A        
-%7D%0A
+    %7D%0A    
         int col 
@@ -982,24 +982,28 @@
 th;%0A        
+  
+  
 int m = Math
@@ -1010,32 +1010,36 @@
 .min(row, col);%0A
+    
         int n = 
@@ -1066,16 +1066,20 @@
         
+    
 //indica
@@ -1127,16 +1127,20 @@
         
+ 
+   
 boolean 
@@ -1165,24 +1165,28 @@
 ow;%0A        
+   
+ 
 int res = In
@@ -1202,16 +1202,20 @@
 _VALUE;%0A
+    
         
@@ -1256,16 +1256,20 @@
         
+    
 int%5B%5D ar
@@ -1286,16 +1286,20 @@
 int%5Bn%5D;%0A
+    
         
@@ -1329,16 +1329,20 @@
 o row i%0A
+    
         
@@ -1388,24 +1388,28 @@
             
+    
 int val = 0;
@@ -1405,24 +1405,28 @@
 nt val = 0;%0A
+    
             
@@ -1477,32 +1477,36 @@
                 
+   
+ 
 set.add(0);%0A    
@@ -1501,16 +1501,20 @@
 add(0);%0A
+    
         
@@ -1568,32 +1568,36 @@
                 
+    
 for (int p = 0; 
@@ -1630,16 +1630,20 @@
         
+  
+  
 array%5Bp%5D
@@ -1698,16 +1698,20 @@
 p%5D%5Bj%5D);%0A
+    
         
@@ -1764,16 +1764,20 @@
         
+    
 //use  T
@@ -1856,16 +1856,20 @@
         
+ 
+   
 Integer 
@@ -1915,24 +1915,28 @@
             
+   
+ 
 if (null != 
@@ -1941,24 +1941,28 @@
 = subres) %7B%0A
+    
             
@@ -2020,34 +2020,42 @@
                 
+ 
-%7D%0A
+   %7D%0A    
                 
@@ -2068,24 +2068,28 @@
 t.add(val);%0A
+    
             
@@ -2106,26 +2106,32 @@
         
-%7D%0A
+    %7D%0A  
         
 %7D%0A      
@@ -2122,26 +2122,31 @@
         
-%7D%0A
+  %7D%0A   
         
 return r
@@ -2133,24 +2133,25 @@
 %0A           
+ 
 return res;%0A
@@ -2150,16 +2150,26 @@
 rn res;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 363