算法：最长递增子序列
发布时间
阅读量：
阅读量
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组衍生而来的序列，在选择性地删除或不进行删除操作的同时能够保持其他元素原有的排列顺序。例如，在不影响其余元素顺序的前提下，[3,6,2,7] 可以被视为 [0.3.1.6.2.2.7] 这个数组的一个子序列
输入：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;
}
总结
- 动态规划是一种直观且易于理解的方法，其计算复杂度为 O(n^2)。
- 优化方法借助于二分查找将计算复杂度降低了 O(n \log n)，特别适合处理规模较大的数据。
期待这个解答能协助您理解最长递增子序列问题的具体解决方案！如有任何疑问，请随时提出进一步交流的机会。
全部评论 (0)
还没有任何评论哟~