甘肃省住房与城乡建设厅网站,建筑网上接活平台,电脑广告设计软件,南召微网站建设最长递增子序列的长度 _ 贪心二分查找 _ 20230510
前言
最长递增子序列的程序一般采用动态规划方式#xff0c;使用bottom-up的数组记忆方式比较容易理解#xff0c;当然也可以采用top-down的递归模式。本文主要讨论如何利用贪心策略#xff0c;同时辅助以二分查找的方式实…最长递增子序列的长度 _ 贪心二分查找 _ 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[k1]nums[i]
过程演示
以nums[3, 6, 4, 8,7]为例进行示例说明定义数组d[n1]数组中储存待维护的元素数组的长度为截止至下标为i的nums的最长子序列的长度。
第一步操作进行初始化 dp[1]{3}
第二步操作插入元素6由于d[1]6所以直接令d[2]6, d{3,6}
第三步操作内部替换元素由于4比d[2]小所以采用二分法在d中寻找第一个小于4的数据位置k,通过查找k1那么更新d[k1]d[2]4, 此时d{3,4}
第四步操作插入元素8由于d[2]8所以直接在尾部插入元素8更新d数组并且数组长度增加1更新后的d数组为d{3,4,8}
第五步操作内部元素替换由于7d[3]所以采用二分法在d当中寻找第一个小于7的元素位置k,通过查找k2,更新d数组d{3,4,7}
整个过程完毕后d数组的长度为3所以nums数组的最长子序列长度为3整个流程结束。
二分程序实现
程序实现过程中的难点为二分查找方法这里我们介绍两种实现方式此两种实现方式差异很小但是反映了不同的处理思路
4.1 通过辅助变量定义查找位置
前面我们探讨了k位置查询实际上k位置要满足的条件为d[k-1]nums[i]d[k]它要找的位置为第一个在d数组中小于nums[i]的位置那么我们可以辅助单变量pospos记录这个位置。
对pos初始化为0处理这样一种情况如果nums[i]比dp数组中的最小值还要小那么就需要采用pos的默认值0。
low1;highlen;pos0;while(lowhigh){mid(lowhigh)/2;if (d[mid]nums[i]){posmid;lowmid1;}else{highmid-1;}}d[pos1]nums[i];}4.2 通过利用high变量实现
如果仔细研究二分法就可以看出辅助变量的位置和high值相等所以可以在查询结束后直接采用high的值此时lowhigh。
程序实现为 low1;highlen;while(lowhigh){mid(lowhigh)/2;if (d[mid]nums[i]){lowmid1;}else{highmid-1;}}d[high1]nums[i];}小结
通过对最长递增子序列的长度的贪心策略回顾我们使用两种二分查找方式查询带替换元素的位置加深了对二分查找位置的理解同时也开阔了最长递增子序列的解题思路。
参考资料
300. 最长递增子序列 - 力扣Leetcode
