#### Longest Alternating Subsequence

P
```package com.thealgorithms.dynamicprogramming;

/*

* 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
*/
public class LongestAlternatingSubsequence {

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

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

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

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

for (int i = 0; i < n; i++) {
las[i] = las[i] = 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] */
if (arr[j] < arr[i] && las[i] < las[j] + 1) {
las[i] = las[j] + 1;
}

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

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

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));
}
}
```  