Longest alternating subsequence

Problem Statement

Given an array of integers arr[], find the length of the longest alternating subsequence. A sequence is alternating if its elements alternate between increasing and decreasing. That is, a[0] < a[1] > a[2] < a[3] > ... or a[0] > a[1] < a[2] > a[3] < ...

Example:

• Input: arr = [1, 5, 4]

• Output: 3

• Explanation: The entire array [1, 5, 4] is alternating: 1 < 5 > 4.

• Input: arr = [1, 4, 5]

• Output: 2

• Explanation: [1, 5] or [1, 4] are alternating subsequences of length 2.

Noob-Friendly Explanation

Imagine you're walking on a hilly path and you want to find the longest stretch where you keep going up-down-up-down (like a zigzag). You can skip some hills but can't rearrange them. That zigzag pattern is an alternating subsequence.

For [1, 5, 4]: you go UP to 5, then DOWN to 4 — that's a perfect zigzag of length 3!

Approach 1: Brute Force (Recursion)

Intuition

At each position, we decide whether to include or skip the element. We track whether the next element should be greater or smaller than the current one.

Algorithm

1. For each element, try including it in the subsequence or skipping it.
2. If including, check if it maintains the alternating property.
3. Return the maximum length found.

class Solution {
    public int longestAltSubseq(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        // Try starting with an increase or a decrease
        return Math.max(
            solve(arr, 0, -1, true),   // next should go up
            solve(arr, 0, -1, false)   // next should go down
        );
    }

    // goUp: true means we need next element to be greater than previous
    private int solve(int[] arr, int index, int prevIndex, boolean goUp) {
        if (index == arr.length) return 0;

        int skip = solve(arr, index + 1, prevIndex, goUp);

        int take = 0;
        if (prevIndex == -1) {
            // First element, always take
            take = 1 + solve(arr, index + 1, index, !goUp);
        } else if (goUp && arr[index] > arr[prevIndex]) {
            take = 1 + solve(arr, index + 1, index, !goUp);
        } else if (!goUp && arr[index] < arr[prevIndex]) {
            take = 1 + solve(arr, index + 1, index, !goUp);
        }

        return Math.max(take, skip);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - At each index we have two choices: take or skip.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Greedy / DP)

Intuition

We maintain two counters: up (length of longest alternating subsequence ending with a rise) and down (ending with a fall). As we scan the array, if the current element is greater than the previous, we can extend a "down" sequence by going up. If it's smaller, we extend an "up" sequence by going down.

Algorithm

1. Initialize up = 1 and down = 1 (a single element is a valid alternating subsequence).
2. For each consecutive pair of elements:
   • If arr[i] > arr[i-1], then up = down + 1 (we went up after a down).
   • If arr[i] < arr[i-1], then down = up + 1 (we went down after an up).
3. The answer is max(up, down).

class Solution {
    public int longestAltSubseq(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;

        // up: length of longest alternating subsequence ending with a rise
        // down: length of longest alternating subsequence ending with a fall
        int up = 1, down = 1;

        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                up = down + 1;
            } else if (arr[i] < arr[i - 1]) {
                down = up + 1;
            }
            // If equal, do nothing
        }

        return Math.max(up, down);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array.
• Space Complexity: O(1) - Only two variables used.