CSES - Increasing Subsequence | Dãy con tăng - LQDOJ: Le Quy Don Online Judge

CSES - Increasing Subsequence | Dãy con tăng

Tác giả:

Dạng bài

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là xác định dãy con tăng dài nhất của mảng, tức là, tìm dãy con dài nhất trong đó tất cả các phần tử đều lớn hơn phần tử trước đó.

Một dãy con là một dãy có thể thu được từ mảng bằng cách xóa một số phần tử mà vẫn không thay đổi thứ tự của các phần tử còn lại.

Input

Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^{5})\) - kích thước của mảng.
Sau đó có \(n\) số nguyên \(x_{1}, x_{2}, \dots, x_{n}\) \((1 \leq x_{i} \leq 10^{9})\) - các phần tử của mảng.