ZigZag - 2003 TCCC Semifinals 3 - TopCoder

Dynamic Programming - Longest Increasing Subsequence( LIS )

It's something like LIS. You have to manipulate the original algorithm to obtain the answer.

I used a two dimensional array ZIGZAG[60][2] such that ZIGZAG[i][0] is the length of the longest ZigZag sequence ending at sequence[i] and ZIGZAG[i][1] is the sign of the last difference ending at sequence[i].

Suppose we have a sequence like this:

1, 8, 7, 6, 9, 10

ZIGZAG[1][0] = 1,          ZIGZAG[1][1] = 0

ZIGZAG[2][0] = 2,         ZIGZAG[2][1] = +1

ZIGZAG[3][0] = 3,         ZIGZAG[3][1] = -1

ZIGZAG[4][0] = 3,         ZIGZAG[4][1] = -1

ZIGZAG[5][0] = 4,         ZIGZAG[5][1] = +1

ZIGZAG[6][0] = 4,         ZIGZAG[6][1] = +1

I implemented the solution in O( n^2 ), since I have to check n items and for each item I will check n items to choose the appropriate subsequence.