2003 TCCC Semifinals 3 - Division I, Level One - ZigZag

Problem Statement:        ZigZag

Solutions:

I solve this problem with help of One-Dimension DP.

I used two one-dimension array with name dp and dif.
dp[i] stores the length of longest zigzag sub sequence that ended to element i of our input sequence.
dif[i] stores the difference between 2 last element for that longest zigzag sub sequence that ended to element i and set dif[i] for each i to 0.

Each element of input sequence can be a zigzag sequence lonely. So the initial state of my solution is to set each element of dp to 1, that means the minimum length for zigzag sub sequences that ended to each element is 1, included only that element.
But how to get the result for dp[i] and dif[i]?

Element i could come as the last element for the longest sequences that ended to element 0,1,..., i-1. So we should check:

1) If the element i could continue the zigzag sequence that ended to element 0,1,...,i-1?
2) If this new zigzag sub sequence is longer than before?

Then we can update dp[i] and dif[i].
After that we should find the biggest number in dp as the answer for this problem.

Here's my code for this problem:

ZigZag_DP.cpp