LC 300. Longest increasing subsequence

class Solution {
    /**
     Violence law  + dp
     Ideas : 
        dp[i]  Express ,  Must be in the form of  i  The length of the longest incrementing subsequence ending at positions 
             Every time I get to a position ,  You have to go back and scan the array ,  If there is 
             An array smaller than the value of the current position ,  From him  dp  Get its length from  + 1
             You can get  dp[i]  A possible value of the current position ,  Go to  0...i - 1 
             The maximum value of all possible values in this interval ,  Namely  dp[i]  The answer to the position , 
             If  0...i - 1  The values in this interval are all higher than  nums[i]  Big ,  that  
            dp[i] = 1 
     */
    public int lengthOfLIS(int[] nums) {
        int N = nums.length;
        if (N == 1) return 1;   //  If the array length position ,  Then the longest increasing subsequence is  1
        // dp[i]  Express ,  Must be in the form of  i  The length of the longest incrementing subsequence ending at positions 
        int[] dp = new int[N];
        dp[0] = 1;  // dp[0]  Must be  1
        int ans = 1;
        for (int i = 1; i < N; i++) { 
            dp[i] = 1;
            //  scanning  0...i-1  Possible values of the area 
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j])  //  Find a possible value 
                    //  Take the biggest one 
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

class Solution {
    /**
     Two points  + dp
     Ideas : 
        dp  Array meaning ,  arrive  i  Who is the longest increasing subsequence of position 
             First in  dp  The valid region of the array finds the first ratio   current value  nums[i]  Big 
         use  nums[i]  To update this number ;  If you can't find it, append it at the end , size++
         such as :    [10,9,2,5,3,7,101,18]
        i == 0, 10  --> size = 1, dp = [10,0....]      // 0.... Indicates an invalid region 
        i == 1, 9   --> size = 1, dp = [9,0....]
        i == 2, 2   --> size = 1, dp = [2,0....]
        i == 3, 5   --> size = 2, dp = [2,5,0...]       
        i == 4, 3   --> size = 2, dp = [2,3,0...]
        i == 5, 7   --> size = 3, dp = [2,3,7,0...]
        i == 6, 101 --> size = 4, dp = [2,3,7,101,0...]
        i == 7, 18  --> size = 4, dp = [2,3,7,18,0...]

         because  dp  Arrays are ordered ,  So we can quickly determine the location through binary search 
         Overall time complexity  O(n * log n)
     */

    public int lengthOfLIS(int[] nums) {
        int N = nums.length;
        if (N == 1) return 1;
        int[] dp = new int[N];
        int size = 1;

        dp[0] = nums[0];
        for (int i = 1; i < N; i++) {
            //  look for  dp  The first ratio in the array  nums[i]  Big 
            int mostLeftBigIndex = search(dp, size, nums[i]);
            if (mostLeftBigIndex == -1) {
                //  If you can't find it ,  Append after 
                dp[size++] = nums[i];
            } else {
                //  eureka ,  Use the value of the current position ,  to update  dp  Corresponding position of 
                dp[mostLeftBigIndex] = nums[i];
            }
        }
        return size;
    }
    //  Two points search ,  Find the first ratio in the array  key  Big 
    private int search(int[] dp, int size, int key) {
        int l = 0, r = size - 1;
        int res = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (dp[m] >= key) {
                res = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return res;
    }
}