最长递增子序列

发布网友发布时间：2024-10-14 10:28

共1个回答

热心网友时间：2024-11-06 00:41

最长递增子序列（Longest Increasing Subsequence，LIS）问题旨在找到特定数组中的最长单调递增子序列。例如，在序列 { 3，5，7，1，2，8 } 中，最长递增子序列长度为4，为 { 3，5，7，8 }。

一、动态规划法

动态规划策略的核心在于建立状态转移方程，假设数组长度为n。设dp[i]表示以数组第i个元素结尾的最长递增子序列长度，初始值为1。数组中每个元素与前i-1个元素比较，当当前元素大于前一个元素时，更新dp[i]为dp[j]+1（其中j<i且dp[j]最大），这样dp[i]将包含以第i个元素结尾的最长递增子序列长度。

时间复杂度：O(n^2)

实现：通过两层循环实现动态规划，第一层循环遍历数组元素，第二层循环比较前一个元素，更新dp数组。

二、二分查找法

该方法利用二分查找降低时间复杂度。首先，创建一个辅助数组B，用于存储当前递增子序列的元素。遍历原数组A中的每个元素，二分查找B数组中是否能找到一个满足条件的元素插入。若找到，则更新B数组的相应位置；若未找到，则在B数组末尾追加当前元素。最后，B数组的长度即为最长递增子序列的长度。

时间复杂度：O(nlogn)

实现：使用二分查找算法插入元素至B数组，并记录B数组长度作为答案。