AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
我要出去乱说
,
2021-01-28 12:33:54
,
所有人可见
,
阅读 340
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
vector<int> stk;
int main()
{
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i ++ ) cin >> arr[i];
stk.push_back(arr[0]);
for (int i = 1; i < n; i ++ )
if (arr[i] > stk.back())
stk.push_back(arr[i]);
else //将栈内第一个大于等于arr[i]的数字替换成arr[i]
*lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
cout << stk.size() << endl;
return 0;
}