Dãy con Bitonic dài nhất

General
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$
Draft saved