LongestAlternatingSubsequence.java

public class LongestAlternatingSubsequence {
    
    // Function to find the length of the Longest Alternating Subsequence
    public static int longestAlternatingSubsequence(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        
        // Arrays to store the length of the longest alternating subsequence ending at each index
        int[] up = new int[n];   // up[i] stores length of LAS ending at i where the last step is increasing
        int[] down = new int[n]; // down[i] stores length of LAS ending at i where the last step is decreasing

        // Initialize the arrays
        up[0] = 1;    // The first element is an alternating subsequence of length 1
        down[0] = 1;  // The first element is also a decreasing subsequence of length 1

        // Fill up the up and down arrays
        for (int i = 1; i < n; i++) {
            up[i] = 1;  // Every element has at least length 1 subsequence (itself)
            down[i] = 1;

            // Check for the longest alternating subsequence that can be formed by including arr[i]
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    up[i] = Math.max(up[i], down[j] + 1);  // Increasing step
                }
                if (arr[i] < arr[j]) {
                    down[i] = Math.max(down[i], up[j] + 1);  // Decreasing step
                }
            }
        }

        // The result will be the maximum length of the subsequence ending at any index
        return Math.max(up[n - 1], down[n - 1]);
    }

    public static void main(String[] args) {
        // Example input
        int[] arr = {1, 7, 4, 9, 2, 5};

        // Output the length of the Longest Alternating Subsequence
        System.out.println("Length of Longest Alternating Subsequence: " + longestAlternatingSubsequence(arr));
    }
}