给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是[2,3,7,101]，它的长度是4。
说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
解法1：动态规划 算法复杂度 O(n^2)
1.建立表 length[n]
2.遍历到nums[i]时，建立循环j in 0-(i-1) 如果nums[j]比nums[i]小，length[i]=max(length[i], length[j]+1)
3.更新maxLength
注：这里额外设置了一个maxlength，是因为nums[i]可能没有起作用
length[i]不表示截止nums[i]的最长增长子序列长度
class Solution {
public:
int FindMax(int a, int b){
return a>b ? a:b;
}
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
) ;
int length[n];
;
length[] = ;
;i<n;i++){
length[i] = ;
;j<i;j++){
if(nums[i] > nums[j]){
length[i] = FindMax(length[i], length[j]+);
}
}
max = FindMax(max, length[i]);
}
return max;
}
};
解法2：算法复杂度 O(nlogn)
1. 新建立一个数组new[]存放值
2. 遍历原数组nums[]
3. 将nums[i]放入new[]中：找到第一个大于nums[i]的值并替换，如果不存在就直接放到new[]末尾
4. 最后的长度即为这个数组new的长度，但是！！这个数组的内容并不是真实最长增长子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
; i < nums.size(); ++i) {
, right = dp.size();
while (left < right) {
;
;
else right = mid;
}
if (right >= dp.size()) dp.push_back(nums[i]);
else dp[right] = nums[i];
}
return dp.size();
}
};