题目描述 给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
思路 动态规划+二分查找 实现O(nlogn)的时间复杂度
代码
class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; //最长上升子序列为2, 3, 7, 18 //len++ int len = 0; for(int num : nums){ int index = Arrays.binarySearch(dp, 0, len, num); //二分查找未找到时返回的下标为-(low+1) //实际插入位置：pos = -(index + 1) if(index < 0){ index = -(index + 1); } dp[index] = num; if(index == len){ len++; } } return len; } }