Dãy Con Tăng Dài Nhất O(N log N) (LIS)
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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:
Nsố nguyênA[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
Community Discussion