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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone , nhphucqt
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.

Output

  • In độ dài của dãy con tăng dài nhất.

Example

Test 1

Input 
8
7 3 5 3 6 2 9 8
Output 
4

Bình luận