// // Solution 1: DP
// // Time complexity: O(n^2)
// // Space complexity: O(n)
// class Solution {
//     public int lengthOfLIS(int[] nums) {
//         final int n = nums.length;
//         int[] dp = new int[n];
//         Arrays.fill(dp, 1);
//         for (int i = 0; i < n; ++i)
//             for (int j = 0; j < i; ++j)
//                 if (nums[i] > nums[j])
//                     dp[i] = Math.max(dp[i], dp[j] + 1);
//         int ans = Integer.MIN_VALUE;
//         for (int e : dp)
//             ans = Math.max(ans, e);
//         return ans;
//     }
// }

// Solution 2: DP + Greedy + Binary Search / Patience Sort
// dp[i] := smallest tailing number of a increasing subsequence of length i + 1.
// dp is an increasing array, we can use binary search to find the index to insert/update the array.
// ans = len(dp)
// Time complexity: O(nlogn)
// Space complexity: O(n)
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> dp = new ArrayList<>();
        for (int x : nums) {
            int it = lower_bound(dp, x, 0, dp.size());
            if (it == dp.size())
                dp.add(x);
            else
                dp.set(it, x);
        }
        return dp.size();
    }
    private int lower_bound(List<Integer> A, int val, int l, int r) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (A.get(m) >= val)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
}

@@ -984,13 +984,20 @@
 ist%3C
+Integer
 %3E();%0A
-
     
@@ -1075,16 +1075,57 @@
 size());
+ // %E6%B3%A8%E6%84%8F%EF%BC%9A%E8%BF%99%E9%87%8Cbinary search%E7%9A%84%E5%AF%B9%E8%B1%A1%E6%98%AFdp%E6%95%B0%E7%BB%84%EF%BC%8C%E8%80%8C%E4%B8%8D%E6%98%AFnums%E6%95%B0%E7%BB%84%E3%80%82
 %0A       
@@ -1149,16 +1149,17 @@
 .size())
+ 
 %0A       
@@ -1264,24 +1264,131 @@
 ze();%0A    %7D%0A
+    // lower_bound%E6%96%B9%E6%B3%95%E5%8F%82%E8%80%83%E8%8A%B1%E8%8A%B1%E5%86%99%E7%9A%84%E4%BB%A3%E7%A0%81%E5%9C%B0%E5%9D%80%EF%BC%9Ahttps://zxi.mytechroad.com/blog/algorithms/binary-search/sp5-binary-search/%0A
     private 
@@ -1562,16 +1562,16 @@
  r = m;%0A
-
         
@@ -1570,32 +1570,33 @@
             else
+ 
 %0A               

update LongestIncreasingSubsequence.java