题目描述：
给出一个整数数组nums，找出其中最长严格递增子序列的长度。
数据范围： $1\le nums.len \le 2500$
题解：
$O(n^2)$ 做法：
使用 $dp[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列的长度，则
需要两个循环遍历， $O(n^2)$ 。
$O(n\log(n))$ 做法：
可以使用线段树或树状数组优化dp，应该可以 $O(n\log(n))$ 解决。
也可以使用这个二分的做法：使用 $dp[i]$ 表示长度为 $i$ 的递增子序列结尾的最小值，使得序列末尾的值尽可能的小，这样才能更多的延长该子序列，是一种贪心的做法。
使用len维护目前得到的子序列长度，则 $dp[1\cdots len]$ 皆存在。每次遇到 $nums[i]$ 时判断是否能接在 $dp[len]$ 的末尾，如果可以，则可以得到长度为 $len + 1$ 的子序列，则 dp[++len] = nums[i]。否则的话可以考虑使用 $nums[i]$ 替换某个长度子序列的末尾元素，使用二分查找出第一个大于等于 $nums[i]$ 的位置，进行修改。最后返回 len + 1。
记录答案：
可以使用 $pre[i]$ 表示将当前 $nums[i]$ 接在末尾时前一个下标是谁。那样的话 $dp$ 数组不能存值，只能存下标了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int ans = 1;
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[i] > nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
|
直接使用原数组进行dp可以省空间，但是只能使用 $dp[len - 1]$ 表示长度为 $len$ 的序列的末尾数字了。
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int lengthOfLIS(vector<int> &nums)
{
int len = 1;
for (int i = 1; i < nums.size(); ++i)
{
int index = lower_bound(nums.begin(), nums.begin() + len, nums[i]) - nums.begin();
if (nums[i] > nums[len - 1])
{
nums[len++] = nums[i];
}
else
{
nums[index] = nums[i];
}
}
for(int i = 0; i < len; ++i)
{
cout << nums[i] << endl;
}
return len;
}
};
|