Dãy Con Tăng Nghiêm Ngặt Dài Nhất

Binary-search Dynamic Programming
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một dãy số nguyên $A$ gồm $N$ phần tử. Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất (Longest Increasing Subsequence). Một dãy con được tạo bằng cách xóa đi một số (có thể không xóa) phần tử mà không làm thay đổi thứ tự các phần tử còn lại.

Dữ liệu vào
  • Dòng đầu: số nguyên dương $N$ $(1 \le N \le 10^5)$.
  • Dòng thứ hai: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(|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.
Ví dụ
Input Output
6\n10 9 2 5 3 7 3
5\n5 4 3 2 1 1
Giới hạn
  • $1 \le N \le 10^5$
  • $|a_i| \le 10^9$
  • Thời gian: 1 giây
  • Bộ nhớ: 256 MB
Draft saved