Leetcode300最长递增子序列

给你一个整数数组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求解问题常规方法思路是采用动态规划，时间复杂度为O(n^2)。classSolution{publicintlengthOfLIS(int[]nums){//定义dp数组//dp[i]表示以nums[i]结尾的最长增量子序列的长度int[]dp=newint[nums.长度];//初始值用1填充（子序列至少包含当前元素本身）Arrays.fill(dp,1);for(inti=0;inums[j]){dp[i]=Math.max(dp[i],dp[j]+1);}}}//遍历dp数组，找到最大值intres=0;对于(inti=0;i=判断大小，即不替换顶部元素returnarr.findIndex(item=>item>=n);}为了进一步优化，可以将findIndex方法替换为二分查找，时间复杂度降低到O(nlogn)。参考精读《DOM diff 最长上升子序列》