AcWing 896. 最长上升子序列 II
原题链接
中等
作者:
AC_
,
2021-01-28 21:05:04
,
所有人可见
,
阅读 305
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int f[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
int idx = 0;
f[0] = -2e9;
for (int i = 0; i < n; i ++) {
if (a[i] > f[idx]) f[++idx] = a[i];
else {
int l = 0, r = idx;
while (l < r) {
int mid = l + r + 1 >> 1;
if (f[mid] < a[i]) l = mid;
else r = mid - 1;
}
f[l + 1] = a[i];
}
}
printf("%d", idx);
return 0;
}