Dãy con lồi lõm dài nhất

Buổi 71-72 — Ôn tập Dynamic Programming
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved