Dãy Con Lượn Sóng Dài Nhất

Dynamic Programming greedy
Points
52
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 lượn sóng (wiggle) nếu hiệu giữa các cặp phần tử liên tiếp luân phiên dương và âm (tức là $b_1 < b_2 > b_3 < b_4 \dots$ hoặc $b_1 > b_2 < b_3 > b_4 \dots$). Dãy có 1 phần tử cũng là dãy lượn sóng. Cho dãy $A$ gồm $N$ số nguyên, hãy tìm độ dài dãy con lượn sóng dài nhất.

Dữ liệu vào
  • Dòng đầu: số nguyên dương $N$ $(1 \le N \le 10^5)$.
  • Dòng thứ hai: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(|a_i| \le 10^9)$.
Dữ liệu ra
  • In ra độ dài dãy con lượn sóng dài nhất.
Ví dụ
Input Output
6\n1 7 4 9 2 5 6
5\n1 2 3 4 5 2
Giới hạn
  • $1 \le N \le 10^5$
  • $|a_i| \le 10^9$
  • Thời gian: 1 giây
  • Bộ nhớ: 256 MB
Draft saved