LongestZigZagSubSequence.java

/*
    Problem: Given an array of integers, find the longest zigzag subsequence.
    This is an extension of the longest increasing subsequence
 */
public class LongestZigZagSubsequence {
    // complexity: time O(n^2), space O(n)
    static int findLongestZigZag(int[] ary) {
        int n = ary.length;
        // memo[i][0]: increasing subsequence
        // memo[i][1]: decreasing subsequence
        int[][] memo = new int[n][2];
        // initialize
        for (int i = 0; i < n; i++) {
            memo[i][0] = 1;
            memo[i][1] = 1;
        }
        int max = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (ary[j] < ary[i] && memo[i][0] < memo[j][1] + 1) {
                    memo[i][0] = memo[j][1] + 1;
                }
                if (ary[j] > ary[i] && memo[i][1] < memo[j][0] + 1) {
                    memo[i][1] = memo[j][0] + 1;
                }
            }
            max = Math.max(max,Math.max(memo[i][0], memo[i][1]));
        }
        return max;
    }
    public static void main(String[] args) {
        int[] ary = { 10, 22, 9, 33, 49, 50, 31, 60 };
        System.out.println(findLongestZigZag(ary));
    }
}

/*
References:
http://www.geeksforgeeks.org/longest-zig-zag-subsequence/
https://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493
*/