題目描述 [ 最長上升子序列]
給定一個無序的整數(shù)數(shù)組鲤屡，找到其中最長上升子序列的長度疗琉。
示例
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]墅拭，它的長度是 4申眼。
說明:
可能會有多種最長上升子序列的組合啦鸣，你只需要輸出對應的長度即可潮饱。
你算法的時間復雜度應該為 O(n2) 。
進階: 你能將算法的時間復雜度降低到 O(n log n) 嗎?
解題思路
- 首先將第一個元素存入dp數(shù)組诫给；
- 遍歷原數(shù)組香拉，若后面的元素大于dp數(shù)組的最后一個元素，則將其加入到dp末尾蝙搔；
- 否則將它替換掉dp數(shù)組中第一個大于等于它的元素缕溉。
- 最后返回dp的大小即可。
代碼
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp;
for (int j = 0; j < n; j++) {
auto it_l = lower_bound(dp.begin(), dp.end(), nums[j]);
if (it_l == dp.end()){
dp.push_back(nums[j]);
cout << nums[j] << " ";
}
else
*it_l = nums[j];
}
return dp.size();
}
};
