Longest alternating subsequence

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Greedy: count transitions between increases and decreases. Track last direction.

Algorithm

1If n==0: return 0. result=1, dir=0 (none yet).
2For each consecutive pair: if up and dir!=up: result++, dir=up. If down and dir!=down: result++, dir=down.

Common Pitfalls

•Just count direction changes. Equal elements don't contribute. DP also works: up[i] and down[i] arrays.

Longest alternating subsequence.java

Java

// Approach: Greedy. Count alternating peaks and valleys. Increment count whenever sign changes.
// Time: O(n) Space: O(1)
class Solution {
    public int alternatingMaxLength(int[] arr) {
        int n = arr.length;

        int inc = 1;
        int dec = 1;

        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1])
                inc = dec + 1;
            else if (arr[i] < arr[i - 1])
                dec = inc + 1;
        }

        return Math.max(inc, dec);
    }
}

Was this solution helpful?