当前位置：首页 > news >正文

算法：最长递增子序列

news 来源：原创 2024/9/20 9:12:05

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

问题分析

最长递增子序列（Longest Increasing Subsequence, LIS）问题要求我们找到一个数组中的最长严格递增子序列的长度。子序列是通过删除某些元素而不改变剩余元素的顺序得到的。例如，在数组 [10,9,2,5,3,7,101,18] 中，最长递增子序列是 [2,3,7,101]，其长度为 4。

解题思路

动态规划（DP）方法：
- 使用一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
- 初始化 dp 数组，每个位置都为 1（至少每个元素自身可以形成一个长度为 1 的子序列）。
- 对于每个元素 nums[i]，遍历之前的元素 nums[j]（j < i），如果 nums[j] < nums[i]，则更新 dp[i] = max(dp[i], dp[j] + 1)。
- 最终，最长递增子序列的长度为 max(dp)。
优化方法（O(n log n)）：
- 使用一个辅助数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的末尾元素的最小值。
- 遍历 nums 中的每个元素，使用二分查找在 tails 中找到第一个大于或等于当前元素的位置，更新 tails。
- 如果当前元素大于 tails 中的所有元素，则将其添加到 tails 的末尾。
- 最终，tails 的长度即为最长递增子序列的长度。

C++ 实现

以下是使用动态规划和优化方法的 C++ 实现：

动态规划实现

#include <vector>
#include <algorithm>
#include <iostream>int lengthOfLIS(std::vector<int>& nums) {if (nums.empty()) return 0;std::vector<int> dp(nums.size(), 1);for (size_t i = 1; i < nums.size(); ++i) {for (size_t j = 0; j < i; ++j) {if (nums[j] < nums[i]) {dp[i] = std::max(dp[i], dp[j] + 1);}}}return *std::max_element(dp.begin(), dp.end());
}int main() {std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};std::cout << "最长递增子序列的长度为: " << lengthOfLIS(nums) << std::endl;return 0;
}

优化方法实现（O(n log n)）

#include <vector>
#include <algorithm>
#include <iostream>int lengthOfLIS(std::vector<int>& nums) {std::vector<int> tails;for (int num : nums) {auto it = std::lower_bound(tails.begin(), tails.end(), num);if (it == tails.end()) {tails.push_back(num);} else {*it = num;}}return tails.size();
}int main() {std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};std::cout << "最长递增子序列的长度为: " << lengthOfLIS(nums) << std::endl;return 0;
}