LIQ - Dãy con tăng dài nhất ( bản dễ )
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
using namespace std;
const int maxn = 3e4 + 4;
long int n, a [maxn], lis [maxn], t [maxn], p;
int main (void)
{
scanf ("%d", &n);
a [0] = -1e9;
a [n + 1] = 1e9;
for (int i = 1; i <= n + 1; ++i) {
if (i <= n) scanf ("%ld", &a [i]);
int l = 0, r = p;
while (l < r) {
int m = (l + r + 1) / 2;
if (a [t [m]] < a [i]) l = m;
else r = m - 1;
}
lis [i] = l + 1;
if (lis [i] > p) t [++p] = i;
else if (a [i] < a [t [lis [i]]]) t [lis [i]] = i;
}
printf ("%ld\n", lis [n + 1] - 1);
return 0;
}