Longest Alternating Subsequence

The longest alternating subsequence (LAS), also called the zigzag or wiggle subsequence, is built by walking the array once and tracking, at each position, the best zigzag length that currently ends going up versus ending going down — because a valid zigzag can only ever extend from the opposite-direction state, the whole problem collapses from subsequence search into a single forward scan with two running counters.

Recognize the pattern

• The prompt asks for the longest subsequence where consecutive picked elements strictly alternate >, <, >, <, ... (or vice versa) — i.e. every local direction must flip.
• Equivalent phrasings: "zigzag array", "wiggle subsequence", "longest up-down sequence".
• The key structural fact: any optimal LAS consists exactly of the local extrema (peaks and valleys) of the array in order — flat runs and monotone runs contribute at most their first and last element.

Brute force to optimal

Brute force: for every pair of indices, recursively try "take element i as the next up-move" or "next down-move", branching over all subsequences. That's O(2^n) time, O(n) recursion depth.

DP (better): define up[i] = length of the longest alternating subsequence ending at index i whose last step went up, and down[i] similarly for a last step going down. For each i, scan all j < i: if a[j] < a[i], up[i] = max(up[i], down[j]+1); if a[j] > a[i], down[i] = max(down[i], up[j]+1). That's O(n^2) time, O(n) space.

Optimal (greedy O(n)): you never need to look back further than the immediately preceding element, because up[i] only ever needs the best down value seen so far, and that best value is always achieved by the most recent direction flip. So keep two scalars, up and down, and update them from the single previous comparison as you scan left to right.

Complexity, derived

Time: the greedy scan performs exactly one comparison and at most one counter update per adjacent pair — n-1 pairs total, each O(1) work — giving T(n) = O(n). No recurrence needed: it's a flat loop, not recursion.

Space: only two integers (up, down) are live at any time regardless of n, so S(n) = O(1) — a strict improvement over the O(n) arrays the DP version needs.

Worked example: {3, 2, 1, 4}

Answer = max(up, down) = 3, matching the expected LAS {3,2,4} or {2,1,4}. Note step i=2: a second consecutive decrease does not extend down again — down only grows off an up, so a run of decreases collapses to just its first drop.

Java (O(n) time, O(1) space)

class Solution {
    public int longestAlternatingSubsequence(int[] a) {
        int n = a.length;
        if (n == 0) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[i - 1]) {
                up = down + 1;
            } else if (a[i] < a[i - 1]) {
                down = up + 1;
            }
            // a[i] == a[i-1]: equal, no state change
        }
        return Math.max(up, down);
    }
}

Pitfalls

• Equal adjacent elements: ties are neither up nor down — skip them, don't reset counters to 1 or treat as either direction, or you'll under/over-count.
• Wrong initialization: up = down = 1, not 0 — a single element is itself a valid (length-1) alternating subsequence.
• Confusing "alternating values" with "alternating parity": this problem is about relative order (>/<), not odd/even elements — a common misread of the phrase "alternating sequence".
• Trying to greedily pick every other element without checking direction flips — picking based on index parity instead of value comparisons gives wrong answers on inputs like {3,2,1,4}.

When to use / when not

Use the O(n) greedy whenever the objective is purely the alternating-length count over the whole array with no extra constraints — it's optimal and needs no auxiliary memory. Fall back to the O(n^2) DP formulation (or a segment-tree-augmented O(n log n) variant) only if the problem adds constraints the greedy can't express, e.g. "alternating subsequence with a minimum gap between indices" or "count the number of such subsequences" (a different, harder counting problem).

Trade-off vs. Longest Increasing Subsequence (LIS): LIS requires a monotonic run and needs binary search + patience sorting to hit O(n log n); LAS's alternation constraint is actually easier — the greedy exploits that no state ever needs history beyond the last flip, so it beats LIS's own optimal bound with plain O(n).

Takeaways

• LAS reduces to counting direction flips between consecutive elements — only local comparisons matter.
• Two rolling counters (up, down) replace an O(n) DP table because each state only ever needs the other state's most recent value.
• Optimal LAS = the sequence of the array's local extrema, in order.
• Recall: why does a run of three strictly decreasing elements only ever contribute 2 to the LAS length, not 3?

Adapted from the classic "Longest Alternating Subsequence" / "Wiggle Subsequence" problem family (GeeksforGeeks, LeetCode 376); greedy O(n) formulation is the standard competitive-programming solution.