不用DP，有点巧妙。
算法思想：维护一个单调递增的数组。
数组a[i]表示长度为i的子序列的最后一个元素是a[i].
当我们求最长子序列的时候，比方说，{1,3,5}和{1,3,4}这两个子序列长度都是3，但是4比5小所以4的适用范围比5要大，比方说{1,3,4,5}可以构成长度为4的子序列，而{1,3,5,5}却不行。
所以我们要尽可能的使最后一个元素小。
#include<iostream> #include<stack> #include<vector> using namespace std; int main(){ int n; cin>>n; vector<int> a; int num; int length=1; for(int i=0;i<=n;i++){ cin>>num; if(i==0){ a.push_back(num); } if(num<a.back()){ for(int j=0;j<a.size();j++){ if(num<a[j]){ a[j]=num; break; } } } if(num>a.back()){ a.push_back(num); } } cout<<a.size(); }
