dp O(nlogn) dp[i]是 长度为i+1的递增子序列的 能找到的最小的第i大（最大）元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp;
for (int i = 0; i < n; ++i) {
auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
if (it == dp.end()) {
dp.push_back(nums[i]);
} else {
*it = nums[i];
}
}
return dp.size();
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> f;
for (int x : nums) {
auto it = lower_bound(f.begin(), f.end(), x);
if (it == f.end()) {
f.push_back(x);
} else {
*it = x;
}
}
return f.size();
}
};
|
dp O(n2) dp[i]是LIS必须以nums[i]结尾的LIS的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int res = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
};
|