总之，思想就是让 cell 中存储比较小的元素。这样，cell 未必是真实的最长上升子序列，但长度是对的。

子串和子序列的区别在于：子串是连续的，所以只需要较当前元素和前一个元素，如果前一个元素比当前元素大，那就没有当前元素的事了，直接研究子问题就可以了。子序列不是这样，比较完当前元素和前一个元素，如果前一个元素较大，不能直接丢弃当前元素，还可以和前面的其他元素比较，因为子序列不要求连续。

想理解二分查找的做法，可以看这个例子： 1 4 5 3，我们需要构造一个递增双边队列。一开始把 1 加进去，4比1大，所以也直接加到队尾，5比4大，所以直接加到队尾，3比5小，所以需要查找3可以插入的位置，查找完是1的位置，所以用3把1替换掉，之所以要查找替换，是因为我们不在乎序列是什么，我们只在乎序列的长度最长是多少。而要想序列最长，需要各个数字之间的距离最短，而替换的数一定大于被替换的数，所以我们选择替换掉小的数。不能直接插入，不然会改变数字出现的顺序！

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp数组用于存储到当前位置为止的最长递增子序列的长度
        int[] dp = new int[n];

        // // 错误的 base case
        // dp[0] = 1;

        // // 错误的状态转移
        // for (int i = 1; i < n; i++) {
        //     // 不要只关注前一个，要关注前面所有的数，因为我们要的不是连续的字串。如果要连续的话，那就只关注前一个。
        //     dp[i] = nums[i] > nums[i - 1] ? dp[i - 1] + 1 : dp [i - 1];
        // }

        // 初始化dp数组，每个位置的最长递增子序列长度至少为1（包含自身）。重点
        Arrays.fill(dp, 1);

        // 状态转移
        for (int i = 0; i < nums.length; i++) {
            // 遍历i位置之前的所有元素，寻找可以与nums[i]构成递增子序列的元素。重点。
            for (int j = 0; j < i; j++) {
                // 如果nums[i]大于nums[j]，则nums[i]可以接在nums[j]之后构成更长的递增子序列
                // 有可能这一轮没有满足条件的 j，所以 dp[i] 就无法更新。万一下一轮需要用 dp[i] 来更新 dp[i + 1]，
                // 那就做不到。因此我们需要事先把 dp[] 全都初始化为 1.
                if (nums[i] > nums[j])
                    // 更新dp[i]，取当前dp[i]与dp[j]+1的较大值
                    // dp[j] + 1表示在nums[j]的最长递增子序列后加上nums[i]构成新的递增子序列
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        // 遍历dp数组找到最长递增子序列的长度
        int res = 0;
        for (int j : dp) {
            // res记录dp数组中的最大值，即整个数组的最长递增子序列的长度
            res = Math.max(res, j);
        }
        
        // 返回最长递增子序列的长度
        return res;
    }
}

• 时间复杂度：O(n^2)，双层遍历
• 空间复杂度：O(n)

贪心+二分+动态规划

想理解二分查找的做法，可以看这个例子：1 4 7 5 6，我们需要构造一个递增双边队列。一开始把 1 加进去，4比1大，所以也直接加到队尾， 7比4大，所以直接加到队尾，5比7小，所以需要查找5可以插入的位置，查找完是7的位置，所以用5把7替换掉，之所以要查找替换， 是因为我们不在乎序列是什么，我们只在乎序列的长度最长是多少。

而要想序列最长，需要各个数字之间的距离最短，而替换的数一定大于被替换的数，所以我们选择替换掉小的数。

不能直接插入，不然会改变数字出现的顺序！

class Solution {
    public int lengthOfLIS(int[] nums) {
        int size = nums.length;
        // 如果数组的长度小于2，直接返回数组的长度即为最长递增子序列的长度
        if (size < 2) return size;
        
        // arr数组用来维护找到的最长递增子序列
        int[] arr = new int[size];
        // 初始时，将nums的第一个元素放入arr中
        arr[0] = nums[0];
        // arr数组中实际存入的值的数量，即当前最长递增子序列的长度，初始为1
        int res = 1;
        
        for (int i = 1; i < size; i++) {
            // 如果当前元素大于arr数组的最后一个元素，则直接追加到arr末尾
            // 这表示我们找到了一个更长的递增子序列
            if (nums[i] > arr[res - 1]) {
                arr[res] = nums[i];
                // 更新最长递增子序列的长度
                res++;
                continue;
            }

            // 如果当前元素不大于arr的最后一个元素，使用二分查找法找到arr中第一个不小于当前元素的位置，即当前元素插入的位置。
            // 二分结束时，right右边（不包括right）全是大于等于指定数的数，
            // left左边（不包括left）全是小于等于指定数的数，因此我们只需检查最后这个数[left,left+1]即可。寻找大于等于nums[i]的左边界。
            int left = 0, right = res - 1, mid;
            while (left <= right) {
                mid = left + (right - left) / 2;
                // 如果arr[mid]大于等于当前元素，则在左侧区间继续查找
                if (arr[mid] >= nums[i]) {
                    right = mid - 1;
                } else {
                    // 否则在右侧区间查找
                    left = mid + 1;
                }
            }
            // 将找到的位置（left指针的位置）的元素更新为当前元素
            // 这样做是为了保持arr数组的长度代表的最长递增子序列的潜在可能性。注意是left而不是left-1
            arr[left] = nums[i];
        }
        // 返回最终计算的最长递增子序列的长度
        return res;
    }
}

插入数据替换比它大的最小的那个，是为了让ceil数组的最后一个元素变得更小，这样ceil数组才能变得更长。（ceil数组最后一个元素永远是正确的，内部其他元素可能不正确，但是不影响长度）

• 时间复杂度 O(NlogN)：遍历 nums 列表需 O(N)，在每个 nums[i] 二分法需 O(logN)。
• 空间复杂度 O(N)：arr 数组占用线性大小额外空间。