/*

 * Problem Statement: - 
 * Find Longest Alternating Subsequence

 * A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations : 

   x1 < x2 > x3 < x4 > x5 < …. xn or 
   x1 > x2 < x3 > x4 < x5 > …. xn
*/

import java.io.*;

public class LongestAlternatingSubsequence {

	/* Function to return longest alternating subsequence length*/
	static int AlternatingLength(int arr[], int n){
		/*

		las[i][0] = Length of the longest
			alternating subsequence ending at
			index i and last element is
			greater than its previous element

		las[i][1] = Length of the longest
			alternating subsequence ending at
			index i and last element is
			smaller than its previous
			element 

		*/
		int las[][] = new int[n][2]; // las = LongestAlternatingSubsequence

		for (int i = 0; i < n; i++)
			las[i][0] = las[i][1] = 1;

		int result = 1; // Initialize result

		/* Compute values in bottom up manner */
		for (int i = 1; i < n; i++){

			/* Consider all elements as previous of arr[i]*/
			for (int j = 0; j < i; j++){

				/* If arr[i] is greater, then check with las[j][1] */
				if (arr[j] < arr[i] && las[i][0] < las[j][1] + 1)
					las[i][0] = las[j][1] + 1;

				/* If arr[i] is smaller, then check with las[j][0]*/
				if( arr[j] > arr[i] && las[i][1] < las[j][0] + 1)
					las[i][1] = las[j][0] + 1;
			}

			/* Pick maximum of both values at index i */
			if (result < Math.max(las[i][0], las[i][1]))
				result = Math.max(las[i][0], las[i][1]);
		}

		return result;
	}

	public static void main(String[] args)
	{
		int arr[] = { 10, 22, 9, 33, 49,50, 31, 60 };
		int n = arr.length;
		System.out.println("Length of Longest "+"alternating subsequence is " +AlternatingLength(arr, n));
	}
}