https://leetcode.cn/problems/longest-increasing-subsequence/description/
给你一个整数数组 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)) 吗?
- 方案1: 动态规划
/*
dp[i]= max(dp[j])+1,其中0≤j<i且num[j]<num[i]
LIS = max(dp[i]),其中0≤i<n
*/
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
auto const size = nums.size();
vector<int> dp(size);
int ret = 0;
for(int i = 0; i < size; ++i){
int maxLen = 1;
int const val = nums[i];
for(int j = 0; j < i ; ++j){
if(val > nums[j]){
maxLen = max(maxLen,dp[j] + 1);
}
}
dp[i] = maxLen;
ret = max(ret,maxLen);
}
return ret;
}
};
方案2:贪心法+二分查找
class Solution {
public:
int lengthOfLIS(vector<int> & nums) {
auto size = (int)nums.size();
if (size <= 1) {
return size;
}
vector<int> dp(size + 1, 0);
int len = 1;
dp[len] = nums[0];
for (int i = 1; i < size; ++i) {
auto val = nums[i];
if (val > dp[len]) {
dp[++len] = val;
} if (val < dp[len]) {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (dp[mid] < val) {
pos = mid;
l = mid + 1;
} else if (dp[mid] > val){
r = mid - 1;
}else{
pos = mid -1;
break;
}
}
dp[pos + 1] = val;
}
}
return len;
}
};
