最长上升子序列（LIS总结）

定义

最长上升子序列是：

1：只包含ai的子序列

2：满足j<i并且aj<ai

3：子序列长度最长
朴素算法O（n^2） dp+二分（nlogn）

dp数组维护的是以pos位置结尾最小可能的值，如果要打印最长上升子序列路径，开辟新数组path,倒着找合法序列，正序寻找就会出现1 2 4 6（2 8 6 7）这种不合法序列。虽然满足所有ai <aj 但是存在i>j。

vector<int>dp;
for(int i=0; i<n; ++i)
{
    int x;
    cin>>x;
    int pos=lower_bound(all(dp),x)-dp.begin();
    if(pos==cnt)
        dp.pb(x),++cnt;
    else
        dp[pos]=x;
}
cout<<dp.size()<<endl;