一、题目描述
给你一个整数数组 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)) 吗?
二、思路讲解
用dp[i] 表示以i 结尾的序列中，最大递增子序列的长度。那么我们在每个i 处，往前找比自己小的数字（记为j 处），将该处的dp值+1，即是i处的dp值（说明i处的数字可以接在j 处后面组成递增子序列）。dp数组中的最大值即为所求。
三、Java代码实现
class Solution { public int lengthOfLIS(int[] nums) { //数组长度 int len = nums.length; //最后结果 int res = 0; //dp[i]表示以i结尾的序列的最大递增子序列长度 int []dp = new int[len]; //给dp赋初值 for(int i=0; i<len; i++) { dp[i] = 1; } for(int i=0; i<len; i++) { int big = 0; for(int j=0; j<i; j++) { if(nums[j]<nums[i]) { big = Math.max(big, dp[j]); } } dp[i] = big + 1; res = Math.max(res, dp[i]); } return res; } }
时间复杂度： O(N^2)
空间复杂度： O(N)
四、算法优化
进阶要求是要时间复杂度为nlogn。我们的算法的时间复杂度主要为：遍历nums数组，使用n，无法优化；线性遍历[0, i-1) 求dp[i]，使用n。我们可以考虑重新设计dp的思路。
设计一个tail数组，tail[i] 表示长度为i的递增序列的最小末尾数字。例如，4 5 1 9 8 5 序列中，长度为1的递增序列有4，5，1，9，8，5，所以tail[1]为1；长度为1的递增序列有4 5，4 9，4 8，
5 8， 5 9……所以tail[2] 为5；长度为3的递增序列有 4 5 9，4 5 8，所以tail[3] 为8。可以看出，tail为一个递增序列，在查找操作时，我们可以使用二分查找。
那么，我们在计算tail[i]的时候，只需要遍历nums，找到第一个比num大的tail[k]，说明num更适合放在tail[k-1]位置，而不能接在tail[k]位置（接上就不递增了）。如果num比tail中所有数字都大，那就说明num适合接在所有递增序列之后，这时递增序列的长度又可以增加了。
参考：力扣300. 最长递增子序列（动态规划 + 二分查找，清晰图解）
class Solution { public int lengthOfLIS(int[] nums) { //数组长度 int len = nums.length; //tail[i]表示，长度为i的递增序列的最小末尾数字 int []tail = new int[len]; //题目所求 递增序列的最大长度 int resLen = 0; for(int i=0; i<len; i++) { int left = 0; int right = resLen; //二分查找 找到比nums[i]大的tail，若找不到，说明nums[i]适合放在所有序列的末尾，那么就向后更新一个长度 while(left < right) { int mid = (left+right) / 2; if(tail[mid]<nums[i]) { left = mid+1; } else { right = mid; } } tail[left] = nums[i]; //更新长度 resLen = resLen==right? (resLen+1) : resLen; } return resLen; } }
时间复杂度： O(NlogN)
空间复杂度： O(N)
