Dãy con lồi lõm dài nhất
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một dãy số được gọi là dãy 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 đơn điệu tăng ngặt hoặc giảm ngặt cũng được coi là dãy Bitonic).
Cho dãy số nguyên $A$ gồm $N$ phần tử. Hãy tìm độ dài của dãy con (không nhất thiết liên tiếp) là dãy Bitonic dài nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- 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
- Độ dài dãy con Bitonic dài nhất.
Ví dụ
| Input | Output |
|---|---|
| 8 1 11 2 10 4 5 2 1 |
6 |
Giới hạn
- $1 \le N \le 10^5, |A_i| \le 10^9$
Community Discussion