最长递增子序列的长度 _ 贪心+二分查找 _ 20230510

最长递增子序列的长度 _ 贪心+二分查找 _ 20230510

1. 前言

最长递增子序列的程序一般采用动态规划方式，使用bottom-up的数组记忆方式比较容易理解，当然也可以采用top-down的递归模式。本文主要讨论如何利用贪心策略，同时辅助以二分查找的方式实现寻找最长递增子序列的长度。

2. 问题描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,7] 是数组 [3, 6, 4, 8,7] 的子序列。

> >**示例 1：**
输入：nums = [3, 6, 4, 8,7]
输出：3
解释：最长递增子序列是 [3,6,7]，因此长度为 3 。

3. 贪心策略

如果要获得最长子序列，就需要尾部的元素足够小，同时需要确保执行贪心策略之后，形成的新数组递增有序，由于这两个约束条件同时存在，若设定数组d[i]，定义数组的长度len为前i个元素形成的最长子序列的长度。

d[i]数组维护需要涉及到替代操作和尾部插入操作，当原数组中的待考察元素落在当前d[i]的数组区间内，就执行内部替代操作，同时保持d[i]数组长度len保持不变；如果待考察的元素比d[len]值大，那么就进行尾部插入操作，同时数组的长度len增加1。

4. 整体算法

首先需要对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]

4. 过程演示

以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. 二分程序实现

程序实现过程中的难点为二分查找方法，这里我们介绍两种实现方式，此两种实现方式差异很小，但是反映了不同的处理思路，

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];}

5. 小结

通过对最长递增子序列的长度的贪心策略回顾，我们使用两种二分查找方式查询带替换元素的位置，加深了对二分查找位置的理解，同时也开阔了最长递增子序列的解题思路。

参考资料：

300. 最长递增子序列 - 力扣（Leetcode）