Problem Statement  
A sequence of numbers is called a zigzag sequence if the differences
between successive numbers strictly alternate between positive and negative. The
first difference (if one exists) may be either positive or negative. A sequence with
fewer than two elements is trivially a zigzag sequence.
For example, 1,7,4,9,2,5 is a zigzag sequence because the differences
(6,3,5,7,3) are alternately positive and negative. In contrast, 1,4,7,2,5
and 1,7,4,5,5 are not zigzag sequences, the first because its first two differences are positive and
the second because its last difference is zero.
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is
a zigzag sequence. A subsequence is obtained by deleting some number of
elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
  Definition   Class:  ZigZag  Method:  longestZigZag  Parameters:  int[]  Returns:  int  Method signature:  int longestZigZag(int[] sequence)  (be sure your method is public) 
    Constraints    sequence contains between 1 and 50 elements, inclusive.    Each element of sequence is between 1 and 1000, inclusive.   Examples  0)     Returns: 6  The entire sequence is a zigzag sequence. 

 1)    { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 } 
 Returns: 7  There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8. 

 2)     3)    { 1, 2, 3, 4, 5, 6, 7, 8, 9 } 
 Returns: 2  
 4)    { 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 } 
 Returns: 8  
 5)    { 374, 40, 854, 203, 203, 156, 362, 279, 812, 955,
600, 947, 978, 46, 100, 953, 670, 862, 568, 188,
67, 669, 810, 704, 52, 861, 49, 640, 370, 908,
477, 245, 413, 109, 659, 401, 483, 308, 609, 120,
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

 Returns: 36  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
