Dãy Con Tăng Dài Nhất O(N log N) (LIS)

Binary-search Buổi 22 — DP 2D & LIS Dynamic Programming
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho mảng A gồm N số nguyên (1 ≤ N ≤ 2 × 10^5). Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất (Longest Increasing Subsequence - LIS).

Dữ liệu vào (Input)
  • Dòng 1: Số nguyên dương N (1 ≤ N ≤ 2 × 10^5).
  • Dòng 2: N số nguyên A[1], A[2], ..., A[N] (-10^9 ≤ A[i] ≤ 10^9).
Dữ liệu ra (Output)
  • In ra một số nguyên duy nhất là độ dài dãy con tăng nghiêm ngặt dài nhất.
Ví dụ mẫu
Sample Input 1
8
10 9 2 5 3 7 101 18
Sample Output 1
4
Sample Input 2
5
5 4 3 2 1
Sample Output 2
1
Draft saved