LongestBitonicSubsequence.java

/*
    Problem: Given an array of integers, find the longest bitonic subsequence.
    The bitonic sequence creates a peek. For example, {1, 3, 5, 4, 2} is a bitonic
    sequence.
    This is an extension of the longest increasing subsequence.
 */
public class LongestBitonicSubsequence {
    // complexity: time O(n^2), space O(n)
    static int findLongestBitonic(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;
        }
        // fill the rest
        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][0] + 1) {
                    memo[i][0] = memo[j][0] + 1;
                }
                if (ary[j] > ary[i] && memo[i][1] < memo[j][1] + 1) {
                    memo[i][1] = memo[j][1] + 1;
                }
            }
            max = Math.max(max, memo[i][0] + memo[i][1] - 1);
        }
        return max;
    }

    public static void main(String[] args) {
        int arr[] = {
                0, 8, 4, 12, 2, 10, 6, 14, 1, 9,
                5, 13, 3, 11, 7, 15};
        System.out.println(findLongestBitonic(arr));
        int arr2[] = { 10, 22, 9, 33, 49, 50, 31, 60 };
        System.out.println(findLongestBitonic(arr2));
    }
  
  /*
  References:
  http://www.geeksforgeeks.org/dynamic-programming-set-15-longest-bitonic-subsequence/
  */