【每天学习一点算法 2026/04/02】最长递增子序列

每天学习一点算法 2026/04/02题目最长递增子序列给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。动态规划动态规划就是先找规律我们设dp[i]是截至下标 i 处最长严格递增子序列的长度那么dp[i]的值应该等于他之前的最长严格递增子序列长度 1我们需要向前找到nums[j] nums[i]的项找出其中最大的dp值。functionlengthOfLIS(nums:number[]):number{constdpnewArray(nums.length).fill(1)// 初始化dp数组最短子序列都是1// 遍历数组计算 dp 值for(leti1;inums.length;i){// 往前遍历元素计算当前位置最长子序列长度for(letji-1;j0;j--){if(nums[j]nums[i]){// 只有 nums[j] nums[i] 时才有可能是子序列// 找到前方最长的递增子序列 1dp[i]Math.max(dp[i],dp[j]1)}}}returnMath.max(...dp)// 返回最长的子序列长度};贪心算法 二分法这个方法是看了官方题解才知道的这个方法的核心就是我们如果要保证子序列最长递增那就得使每个上升的元素也就是下一个元素尽可能的小于是我们可以维护一个数组使这个数组的最后一项为递增子序列的最小可能值。我们以这个[10,9,2,5,3,7,101,18]为例第一项 10 只有一项肯定最短[10]接下来 9它是小于 10 , 后面大于 9 的数肯定是比大于 10 的数多的直接替换[9]接下来 2同理直接替换[2]接下来 5他是大于我们最后一项 2 的那么我们可以直接将它插入最长子序列[2, 5]接下来 3他是小于 5 的那我们就需要在维护的数组里找到第一个大于它的元素也就是 5 替换掉它[2, 3]接下来 7直接插入[2, 3, 7]接下来 101直接插入[2, 3, 7, 101]接下来 18替换掉第一个大于大的 101[2, 3, 7, 18]其实我们发现这个流程下来得到的结果并不是我们最终的最长子序列比如我们把 3 换成 1最终结果就会变成[1, 5, 7, 18]本来应该是[2, 5, 7, 18]但是我们可以看出遇到小于最后一位我们只做了替换操作不会影响数组的长度因为我们无法保证后续元素中小于末尾的元素个数上面的例子是一个理想的情况感觉只需要替换最后一个元素就行了觉得有疑问的可以尝试一下[9, 10, 1, 2, 3, 4]我们只有不断的往前替换元素才能保证数组的最后一位是可能子序列的最小末尾数。functionlengthOfLIS(nums:number[]):number{constres[nums[0]]//for(leti1;inums.length;i){if(res[res.length-1]nums[i]){letleft0,rightres.length-1,posnums.len-1// 默认替换末尾while(leftright){constmidMath.floor((leftright)/2)if(res[mid]nums[i]){// 由于是向下取整的所以需要在左边处理时记录当前位置为替换位置posmid rightmid-1}else{// 第一个大于 nums[i] 右侧leftmid1}}res[pos]nums[i]// 修改对应位置}else{res.push(nums[i])// 末尾添加}}returnres.length// 返回最终长度};题目来源力扣LeetCode