Ⅰ、动态规划

$dp[i] = max(dp[j]) + 1;\ 0 <= j < i \ \cap num[j] < num[i]$

$LIS_{length} = max(dp[i]); \ 0 <= i < n$

$dp[i]$ 代表前 $i$ 个元素，以第 $i$ 个数字结尾的最长上升子序列长度。
每次遍历一个 $dp[i]$ 就需要从头遍历一遍 $dp[j] \ , 0 <= j < i$ ，更新 $dp[i]$

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        dp[0] = 1;
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

Ⅱ、二分查找 + 贪心

贪心思想：
- 顺序遍历一遍 $nums$ ，为了达到最长的升序序列，尽可能取最小的值到 $tails$ 中
- $tails$ 数组用于存放最长子序列，所以满足条件的都会放进此数组中，此数组肯定是升序的
- 在升序中可以用二分查找，尽快找到当前遍历的需要存放的位置，二分范围
  - $num > \forall \ tails[\,]$ ，可以直接插入到 $tails$ 最后位置，二分出来的结果 $l$ 在最后，此时“扩容” res++
  - $else$ 二分找到最靠近前面位置的可插入位置，然后覆盖插入，不需要扩容
准备一个 $tails[n]$ ， $res$ 即作为结果，同时也是二分查找的右边界
最终的 $tails$ 并不是最长子序列的结果，但是数组的长度是正确的，即 res

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int res = 0;
    for (int num : nums) {
        int l = 0, r = res; // 确定好 tails 区间范围
        while (l < r) {
            int mid = l + ((r - l) >>> 1);
            if (num > tails[mid])
                l = mid + 1;
            else
                r = mid;
        }
        tails[l] = num; // 当前值替换二分找到的 l 位置
        if (res == r) res++; // 需要“扩容”
    }
    return res;
}