Dãy Đổi Dấu Dài Nhất

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một dãy số được gọi là dãy đổi dấu nếu hiệu giữa các phần tử liên tiếp luân phiên dương và âm (tức là $x_1 < x_2 > x_3 < x_4 \dots$ hoặc $x_1 > x_2 < x_3 > x_4 \dots$). Dãy gồm $1$ phần tử hoặc $2$ phần tử khác nhau luôn được coi là dãy đổi dấu.

Cho dãy $N$ số nguyên $a_1, a_2, \dots, a_N$. 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 đổi dấu.

Cấu trúc con tối ưu: duy trì hai trạng thái $up$ (độ dài lớn nhất kết thúc bằng bước tăng) và $down$ (độ dài lớn nhất kết thúc bằng bước giảm).

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, \dots, a_N$ ($|a_i| \le 10^9$).
Dữ liệu ra
  • In ra độ dài dãy con đổi dấu dài nhất.
Ví dụ
Input Output
6\n1 7 4 9 2 5 6
10\n1 17 5 10 13 15 10 5 16 8 7
Giới hạn
  • $1 \le N \le 10^5$
  • $|a_i| \le 10^9$
Draft saved