Dãy Con Tăng Dài Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng gồm $n$ số nguyên. Tìm độ dài dãy con tăng ngặt dài nhất (Longest Increasing Subsequence — LIS). Dãy con thu được bằng cách xóa một số phần tử mà không thay đổi thứ tự, và mỗi phần tử phải lớn hơn phần tử trước đó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ : kích thước mảng.

Dòng thứ hai chứa $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ : các phần tử của mảng.

Dữ liệu ra

In ra độ dài dãy con tăng ngặt dài nhất.

Ràng buộc

$1 \leq n \leq 2 \times 10^{5}$
$1 \leq x_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
10 1 1 1 1 1 1 1 1 1 1	1	Tất cả phần tử bằng nhau, LIS có độ dài $1$
10 1 2 3 4 5 6 7 8 9 10	10	Mảng đã tăng ngặt, LIS là toàn bộ mảng

Bình luận

Không có bình luận tại thời điểm này.