Đoàn tàu tăng tốc dài nhất
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Dãy con tăng dài nhất (LIS)
Cho mảng gồm $N$ số nguyên $a_1, a_2, \dots, a_N$.
Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất. Dãy con của một mảng là một dãy thu được bằng cách xóa đi một số phần tử (hoặc không xóa phần tử nào) mà không làm thay đổi thứ tự tương đối của các phần tử còn lại.
Dữ liệu vào
- Dòng 1: Số nguyên dương $N$ ($1 \le N \le 10^5$).
- Dòng 2: $N$ số nguyên cách nhau bởi dấu cách ($-10^9 \le a_i \le 10^9$).
Dữ liệu ra
In ra một số nguyên duy nhất là độ dài của dãy con tăng nghiêm ngặt dài nhất.
Community Discussion