Another solution for ZigZag

ZigZag.java

public class ZigZag {

	public static int longestZigZag(int[] sequence) {
		final int n = sequence.length;
		
		int[] positive = new int[n];
		int[] negative = new int[n];
		for (int i=0; i<n; ++i) {
			positive[i] = negative[i] = 1;
		}
		
		for (int i=1; i<n; ++i) {
			for (int j=0; j<i; ++j) {
				if (sequence[i] > sequence[j]) {
					negative[i] = Math.max(negative[i], positive[j] + 1);
				} else if (sequence[i] < sequence[j]) {
					positive[i] = Math.max(positive[i], negative[j] + 1);
				}
			}
		}
		
		return Math.max(positive[n-1], negative[n-1]);
	}
}