题目描述
给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数N。
第二行包含N个整数,表示完整序列。
输出格式
输出一个整数,表示最大长度。
数据范围
1≤N≤100000,
−109≤数列中的数≤109
输入样例
7
3 1 2 1 8 5 6
输出样例
4
用动态规划复杂度为n^2
(见acwing 895),用栈可以将复杂度降为nlogn
每输入一个数
如果是 栈为空 或者 此时x大于栈顶元素 则入栈
否则 替换掉第一个大于或等于x的那个数的值
此处用 vector 模拟栈
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>s;//模拟堆栈
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++){
int x;
cin >> x;
if(s.empty() || x > s.back()){ //栈为空 或者 此时x大于栈顶元素
s.push_back(x); // 入栈
}
else{
*lower_bound(s.begin(),s.end(),x)=x;//替换掉第一个大于或等于x的那个数的值
}
}
cout << s.size() << endl; // 输出栈的元素个数
return 0;
}