安平县哪家做网站想做电商应该怎么入门
最长递增子序列的长度 _ 贪心+二分查找 _ 20230510
- 前言
最长递增子序列的程序一般采用动态规划方式，使用bottom-up的数组记忆方式比较容易理解，当然也可以采用top-down的递归模式。本文主要讨论如何利用贪心策略，同时辅助以二分查找的方式实现寻找最长递增子序列的长度。
- 问题描述
给你一个整数数组
nums，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,7]是数组[3, 6, 4, 8,7]的子序列。
> >**示例 1：**
输入：nums = [3, 6, 4, 8,7]
输出：3
解释：最长递增子序列是 [3,6,7]，因此长度为 3 。
- 贪心策略
如果要获得最长子序列，就需要尾部的元素足够小，同时需要确保执行贪心策略之后，形成的新数组递增有序，由于这两个约束条件同时存在，若设定数组d[i]，定义数组的长度len为前i个元素形成的最长子序列的长度。
d[i]数组维护需要涉及到替代操作和尾部插入操作，当原数组中的待考察元素落在当前d[i]的数组区间内，就执行内部替代操作，同时保持d[i]数组长度len保持不变；如果待考察的元素比d[len]值大，那么就进行尾部插入操作，同时数组的长度len增加1。
- 整体算法
首先需要对d[i]数组初始化，并定义其实长度len为1。假定待考察的数组为nums,那么初始化 d[1]=nums[0]，根据d[i]数组的单调性，可以采用二分法寻找内部替代的具体位置。假定当前已求出的最长子序列的长度为len，从前往后遍历数组nums，遍历至当前数据元素nums[i]时：
- 如果nums[i]>d[len]，则直接插入元素，令d[++len]=nums[i]
- 否则,在d数组中进行二分查找，找到第一个小于nums[i]的数据位置k,并更新d[k+1]=nums[i]
- 过程演示
以nums=[3, 6, 4, 8,7]为例进行示例说明，定义数组d[n+1]，数组中储存待维护的元素，数组的长度为截止至下标为i的nums的最长子序列的长度。
第一步操作，进行初始化： dp[1]={3}
第二步操作，插入元素6，由于d[1]<6，所以直接令d[2]=6, d={3,6}
第三步操作，内部替换元素，由于4比d[2]小，所以采用二分法在d中寻找第一个小于4的数据位置k,通过查找k=1，那么更新d[k+1]=d[2]=4, 此时d={3,4}
第四步操作，插入元素8，由于d[2]<8，所以直接在尾部插入元素8，更新d数组，并且数组长度增加1，更新后的d数组为d={3,4,8}
第五步操作，内部元素替换，由于7<d[3]，所以采用二分法在d当中寻找第一个小于7的元素位置k,通过查找k=2,更新d数组d={3,4,7}
整个过程完毕后，d数组的长度为3，所以nums数组的最长子序列长度为3，整个流程结束。
- 二分程序实现
程序实现过程中的难点为二分查找方法，这里我们介绍两种实现方式，此两种实现方式差异很小，但是反映了不同的处理思路，
4.1 通过辅助变量定义查找位置
前面我们探讨了k位置查询，实际上k位置要满足的条件为d[k-1]<nums[i]<d[k]，它要找的位置为第一个在d数组中小于nums[i]的位置，那么我们可以辅助单变量pos，pos记录这个位置。
对pos初始化为0，处理这样一种情况，如果nums[i]比dp数组中的最小值还要小，那么就需要采用pos的默认值0。
low=1;high=len;pos=0;while(low<=high){mid=(low+high)/2;if (d[mid]<nums[i]){pos=mid;low=mid+1;}else{high=mid-1;}}d[pos+1]=nums[i];}
4.2 通过利用high变量实现
如果仔细研究二分法，就可以看出，辅助变量的位置和high值相等，所以可以在查询结束后，直接采用high的值，此时low>high。
程序实现为：
low=1;high=len;while(low<=high){mid=(low+high)/2;if (d[mid]<nums[i]){low=mid+1;}else{high=mid-1;}}d[high+1]=nums[i];}
- 小结
通过对最长递增子序列的长度的贪心策略回顾，我们使用两种二分查找方式查询带替换元素的位置，加深了对二分查找位置的理解，同时也开阔了最长递增子序列的解题思路。
参考资料：
300. 最长递增子序列 - 力扣（Leetcode）