1.题目

给你一个整数数组 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(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(nlog(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

（1）动态规划
① 定义dp数组，dp[i]表示数组nums中以nums[i]结尾的最长递增子序列的长度。
② 确定状态转移方程，假设nums[i] = k，由于是递增子序列，故只要找到前面那些结尾比 k 小的子序列，然后把 k 放到最后，这样就可以形成一个新的递增子序列，而且这个新的子序列长度为dp[i]和dp[j]+1之间的最大值。显然新的子序列非常多，但我们只选择最长的那一个，把最长子序列的长度作为 dp[i] 的值即可，所以可以推出状态转移方程为：if(nums[i]>nums[j]) dp[i]=Math.max(dp[i],dp[j]+1);。
③ 当更新完dp数组后，dp数组中的最大值即为所数组nums中最长递增子序列的长度。
使用动态规划的时间复杂度为O(n2)。
（2）二分搜索
本题可以通过二分搜索将时间复杂度降低到O(nlog(n))，其中也是用到了耐心排序的思想，只不过该方法比较难想到。参考链接如下：从最长递增子序列学会如何推状态转移方程、耐心排序。

3.代码实现（Java）

//思路1————动态规划
public int lengthOfLIS(int[] nums) {
    int length = nums.length;
    //dp[i]:表示数组nums中以nums[i]结尾的最长递增子序列的长度
    int[] dp=new int[length];
    //将dp数组中的所有元素全部初始化为1
    Arrays.fill(dp,1);
    for(int i=0;i<length;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
    }
    //dp数组中的最大值即为所数组nums中最长递增子序列的长度
    int res=0;
    for(int i=0;i<length;i++){
        res=Math.max(res,dp[i]);
    }
    return res;
}

//思路2————二分搜索
public int lengthOfLIS(int[] nums) {
    int length = nums.length;
    //定义堆顶元素数组，top[i]表示第i个堆的堆顶元素
    int[] top=new int[length];
    //堆数初始化为0
    int piles=0;
    for(int i=0;i<length;i++){
        //当前要处理的元素
        int ele=nums[i];
        //搜索左侧边界的二分搜索
        int left=0,right=piles;
        while(left<right){
            int mid=left+(right-left)/2;
            if(top[mid]<ele){
                left=mid+1;
            }else if(top[mid]>ele){
                right=mid;
            }else if(top[mid]==ele){
                //收缩右侧边界
                right=mid;
            }
        }
        //没有找到合适的堆，新建一个堆
        if(left==piles){
            piles++;
        }
        //将该元素放到堆顶
        top[left]=ele;
    }
    //最后得到的堆数即为最长递增子序列的长度
    return piles;
}