Longest Alternating Subsequence

A
```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 final class LongestAlternatingSubsequence {
private 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] = 1;
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));
}
}
```