给你一个整数数组 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)) 吗?

    1. class Solution {
    2.     //f[i] 表示以nums[i]结尾的上升子序列长度
    3.     public int lengthOfLIS(int[] nums) {
    4.         int n = nums.length;
    5.         int[] f = new int[n+1];
    6.         int res = 0;
    7.         for (int i = 0; i < n; i++) {
    8.             f[i] = 1;
    9.             for (int j = 0; j < i; j++) 
    10.                 if (nums[j] < nums[i]) 
    11.                     f[i] = Math.max(f[i], f[j]+1);
    12.             res = Math.max(res, f[i]);
    13.         }
    14.         return res;
    15.     }
    16. }

    LIS + 二分

    1. class Solution {
    2.     //tails[k]代表长度k+1子序列的尾部元素值
    3.     public int lengthOfLIS(int[] nums) {
    4.         int n = nums.length;
    5.         int[] tails = new int[n];
    6.         int res = 0;
    7.         for (int num : nums) {
    8.             int l = 0, r = res;
    9.             //二分找到第一个大于等于num的下标,如果大于num则直接插入,因为小的数更容易在后面遇到递增子序列
    10.             while (l < r) {
    11.                 int mid = l + r >> 1;
    12.                 if (tails[mid] >= num) r = mid;
    13.                 else l = mid + 1;
    14.             }
    15.             tails[l] = num;
    16.             //如果
    17.             if (res == r) res++;
    18.         }
    19.         return res;
    20.     }
    21. }