Longest Zigzag Subsequence

You are given an array of integers. Your task is to find the length of the longest Zigzag Subsequence that can be obtained from the array. A sequence is called a Zigzag Sequence if the differences between consecutive elements strictly alternate in sign. In mathematical terms, for the subsequence \(a_1, a_2, \dots, a_k\) (with \(k \geq 2\)), the differences \(a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}\) must satisfy either:

• \(a_2 - a_1 > 0,\ a_3 - a_2 0, \dots\)
• \(a_2 - a_1 0,\ a_4 - a_3 < 0, \dots\)

If the array is empty, the answer is 0, and if it contains only one element, the answer is 1.

Implement an efficient solution using dynamic programming.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements. If \(n = 0\), the second line may be omitted.

outputFormat

Output a single integer on standard output (stdout): the length of the longest Zigzag subsequence.

6
1 7 4 9 2 5

6