326. Longest Alternating Subsequence

Given an array of n integers, find the length of its longest alternating (zig-zag) subsequence - one where the elements strictly alternate between rising and falling at every consecutive step (either up-down-up-... or down-up-down-...).

Input: The first line contains an integer n. The second line contains n space-separated integers, the array. Output: Print a single integer - the length of the longest alternating (zig-zag) subsequence.

1 <= n <= 10^4

This problem has BOTH a full O(n²) DP solution (shown here, generalizable to related harder variants) AND a much simpler O(n) greedy solution (just counting alternating direction changes) - knowing both, and why the greedy one works here specifically, is a strong signal.

Find the length of the longest subsequence that strictly alternates between rising and falling at every step. Brute force: Try every possible subsequence directly and check if it alternates correctly, taking the longest - this is exponential (2^n subsequences), impractical for n up to 10^4. Optimised: Tracking TWO separate arrays (one for 'ends in a rise', one for 'ends in a fall') captures both possible 'directions' a valid alternating subsequence could currently be in - cross-updating between them (a rise can only follow a fall, and vice versa) directly enforces the strict alternation requirement.

Scan the array once while tracking a running count (starting at 1), and each time the direction between consecutive elements switches, relative to the previous comparison direction, whether the sequence is currently rising or falling, increment the count. Equal consecutive elements are simply skipped since they cannot contribute to either direction. This works because the longest alternating subsequence is exactly the sequence of local peaks and valleys in the array, and every direction change encountered while scanning left to right corresponds to exactly one extension of that subsequence, so no comparisons against earlier indices are ever needed. Time: O(n) Space: O(1)

Maintain two DP arrays, up[i] and down[i], where up[i] is the length of the longest alternating subsequence ending at index i whose last move was an increase, and down[i] is the same but whose last move was a decrease. For each i, look back at every earlier index j: if arr[j] < arr[i], up[i] can be down[j] + 1, and if arr[j] > arr[i], down[i] can be up[j] + 1, taking the best over all such j. This is correct because any alternating subsequence ending at i must have been extended from a shorter alternating subsequence ending in the opposite direction at some earlier index, and checking all such j guarantees the true optimum is found, at the cost of a quadratic number of comparisons. Time: O(n^2) Space: O(n)

Generate every possible subsequence of the array (by choosing, for each element, whether to include it or not), check whether each generated subsequence strictly alternates between rising and falling at every step, and keep track of the longest one found that qualifies. This is correct because it exhaustively considers every candidate subsequence, but the number of subsequences grows exponentially with the array size, making it impractical beyond very small inputs. Time: O(2^n) Space: O(n)

1. Track TWO arrays: inc[i] = longest alternating subsequence ending at i where the LAST STEP was a RISE, and dec[i] = same but where the last step was a FALL. 2. For j<i: if arr[j]<arr[i], inc[i] can be updated from dec[j]+1 (a fall INTO j, then a rise INTO i). If arr[j]>arr[i], dec[i] can be updated from inc[j]+1 (symmetric). 3. A single element alone has length 1 in both arrays; the final answer is the maximum anywhere across both.

Time: O(n²) - for each index i, checking all earlier indices j. Space: O(n), for the inc[] and dec[] arrays (though an O(n) GREEDY approach also exists, simply counting direction changes as you scan once, since maximizing alternation greedily by taking every local peak/valley is provably optimal here).

Test n = 1 (answer 1), an array with equal consecutive values (which can't extend either an up or down run), and n at the upper bound of 10^4.

Be ready to mention the simpler O(n) greedy alternative (count every local direction change: a strictly increasing-then-decreasing transition, or vice versa) as a more efficient solution than the O(n²) DP - a nice example of a problem that LOOKS like it needs full DP but actually has an elegant greedy shortcut.