最长递增子序列
一、题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
例子：
1
2
3
| 输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
|
Leetcode：https://leetcode.cn/problems/longest-increasing-subsequence/
二、思路
动态规划思路，定义 dp 数组，数组长度为 nums 的长度。当数组 nums 只有第一个元素时，那么最长递增子序列为1；当有 N 个元素的时候，dp[N]的位置的值，应该如何求呢？我们遍历 0 到 N-1 位置，如果 nums[N] > nums[i] ，那么此时就有 dp[N] = max(dp[N], dp[i]+1)。需要注意，此时 dp 数组的最后一个元素不一定是最长递增子序列的长度。因为并没有依次给 dp 数组赋值，而是有条件性的赋值，条件即为：nums[N] > nums[i]。所以我们可以用一个变量来记录最值。
延伸一下，如果要这个最长递增子序列呢？而不是求长度。
也比较简单，dp 数组已经记录了以某个位置为结尾的数组的最长递增子序列。那么我们先取到最大的那个位置，依次往前找，比如最后一个位置为 max_pos，依次往前找 i，那么有 dp[i] == dp[max_pos]-1 的时候，既可以取 nums 的位置的元素。
三、代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <vector>
#include <algorithm>
#include <iostream>
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
if (nums.empty()) return 0;
std::vector<int> dp(nums.size(), 0);
int max_val = 0;
for (size_t i = 0; i < nums.size(); ++i) {
dp[i] = 1;
for (size_t j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = std::max(dp[i], dp[j]+1);
}
}
if (dp[i] > max_val) {
max_val = dp[i];
}
}
return max_val;
}
};
class Solution_02 {
public:
std::vector<int> lengthOfLIS(std::vector<int>& nums) {
if (nums.empty()) return std::vector<int>();
std::vector<int> dp(nums.size(), 0);
int max_pos = 0, max_val = 0;
for (size_t i = 0; i < nums.size(); ++i) {
dp[i] = 1;
for (size_t j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = std::max(dp[i], dp[j]+1);
}
}
if (dp[i] > max_val) {
max_val = dp[i];
max_pos = i;
}
}
std::vector<int> res;
res.emplace_back(nums[max_pos]);
int prev = max_pos;
for (int i = max_pos-1; i >= 0; --i) {
if (dp[i] == dp[prev]-1) {
res.emplace_back(nums[i]);
prev = i;
}
}
std::reverse(res.begin(), res.end());
return res;
}
};
void print_vec(const std::vector<int>& vec) {
for (const auto& x : vec) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int main() {
Solution_02 s;
std::vector<int> vec{2, 1, 5, 3, 6, 4, 8, 9, 7};
auto res = s.lengthOfLIS(vec);
print_vec(res);
return 0;
}
|
不过这个方法的时间复杂度是 O(N2)，空间复杂度是 O(n)。这里还有可优化的空间。待优化