[leetcode] interview question 17.08 Circus tower

subject :

 Interview questions  17.08.  Circus tower 
 There's a circus that's designing a lot of shows , One should stand on the shoulder of another . For practical and aesthetic reasons , The person above is shorter and lighter than the person below . We know the height and weight of everyone in the Circus , Please write code to calculate how many people can be stacked at most .

 Example ：

 Input ：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
 Output ：6
 explain ： Count from top to bottom , At most, a man can fold  6  layer ：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
 Tips ：

height.length == weight.length <= 10000

Ideas ：
In ascending order of height , Those of the same height are sorted in descending order of weight , It becomes Longest ascending subsequence （LIS） problem .

class Solution {
    
    public int bestSeqAtIndex(int[] height, int[] weight) {
    
        int len = height.length;
        int[][]person = new int[len][2];
        for(int i = 0; i < len;i++){
    
            person[i] = new int[]{
    height[i],weight[i]};
        }    
        //  Sort height in ascending order , If the height is the same , Weight in descending order 
        Arrays.sort(person,(a , b) -> a[0] ==  b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] dp = new int[len]; //dp Storing elements that may form the longest subsequence 
        int res = 0; // Store the longest subsequence length 
        for(int[] pair : person){
    
            // ( Dichotomy ： Get the value of the longest substring )
            //  In subscript 0~res Search between pair[1] The subscript ( Two points search pair[1] In the sorted dp Index in array )
            int i = Arrays.binarySearch(dp,0,res,pair[1]);
            if(i < 0) {
      //  If the search is not successful , Return a negative number :- The insertion point -1)  The insertion point   Defined as the point where the key is inserted into the array ： That is, the first element index greater than this key 
                i = -(i + 1);  //  Find the insertion point 
            }
            dp[i] = pair[1]; // If i<res, The description replaces the original dp The greater of , Smaller values enter the array , It is convenient for latecomers to expand the actual number of elements of the array , Increase the sequence length 
            if(i == res) {
      // If pair[1] Greater than dp All elements in , Extend the length of the longest subsequence 
                ++res;
            }
        }
        return res; 
    }
}