Dãy con Bitonic dài nhất
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một dãy số được gọi là Bitonic nếu tồn tại một vị trí đỉnh sao cho các phần tử từ đầu đến đỉnh tăng ngặt, và từ đỉnh đến cuối giảm ngặt (một dãy chỉ tăng ngặt hoặc chỉ giảm ngặt cũng được coi là Bitonic).
Cho dãy số nguyên $A$ gồm $N$ phần tử. Hãy tìm độ dài lớn nhất của một dãy con (không nhất thiết liên tiếp) của $A$ là dãy Bitonic.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 2000$).
- Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^9$).
Dữ liệu ra
Một số nguyên duy nhất là độ dài dãy con Bitonic dài nhất.
Ví dụ
| Input | Output |
|---|---|
6<br>1 2 5 3 2 1 |
6 |
Giới hạn
- $1 \le N \le 2000$
- $|A_i| \le 10^9$
Community Discussion