Longest alternating subsequence

The problem, simply

You get a row of numbers. Choose some of them, keeping their order, so that the steps between chosen numbers switch direction every time: up then down then up, or down then up then down. Equal neighbors do not count as a step.

Give back the length of the longest such zigzag. It is called the longest alternating subsequence (LeetCode calls it a wiggle subsequence).

A story to remember it

Picture it

Examples

Way 1: the simple way

Make two tables. up[i] is the longest zigzag that ends at arr[i] with a step up. down[i] is the longest one that ends at arr[i] with a step down. (Trying every choice with plain recursion would be O(2^n); these tables remember the answers instead.)

1. Every number alone: up[i] = down[i] = 1.
2. For each i, look back at every j < i.
3. If arr[j] < arr[i] (a step up), then up[i] = max(up[i], down[j] + 1).
4. If arr[j] > arr[i] (a step down), then down[i] = max(down[i], up[j] + 1).
5. The answer is the biggest value in either table.

class Solution {
    public int longestAltSubseq(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        int[] up = new int[n], down = new int[n];
        int best = 1;
        for (int i = 0; i < n; i++) {
            up[i] = down[i] = 1;                              // the number alone
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) up[i] = Math.max(up[i], down[j] + 1);   // step up
                if (arr[j] > arr[i]) down[i] = Math.max(down[i], up[j] + 1); // step down
            }
            best = Math.max(best, Math.max(up[i], down[i]));
        }
        return best;
    }
}

How long it takes: each number looks back at all earlier ones, O(n^2). Extra room: two arrays, O(n).

Way 2: the clever way

You do not need the whole table. Let up be the best zigzag so far whose last step went up, and down the best whose last step went down, over everything seen so far. Then only neighbors matter:

1. Start with up = down = 1.
2. If arr[i] > arr[i - 1], set up = down + 1.
3. If arr[i] < arr[i - 1], set down = up + 1.
4. If they are equal, change nothing.
5. The answer is max(up, down).

Why only neighbors? If the path keeps climbing, the best zigzag that ends going up might as well end at the highest point of that climb, which is the newest number. So you can always pretend the zigzag uses the number right before this one.

class Solution {
    public int longestAltSubseq(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        int up = 1, down = 1;   // best zigzag whose last step went up / down
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) up = down + 1;        // a step up turns a down-ending zigzag
            else if (arr[i] < arr[i - 1]) down = up + 1;   // a step down turns an up-ending zigzag
            // equal neighbors: nothing changes
        }
        return Math.max(up, down);
    }
}

How long it takes: one look at each number, O(n). Extra room: two counters, O(1).

Watch out for

• An empty row must return 0, and a row of one number returns 1.
• In Way 2, do not reset a counter when the direction does not change. The counters only ever grow.
• Some versions demand that the first step is up (a < b > c ...). Then answer up and down with a fixed start, or keep separate counters that remember the first direction.

What interviewers ask next

• Print one zigzag: take the first number, then every number where the direction turns, plus the last number of the run. In other words, keep the peaks and valleys.
• Greedy view: remove equal neighbors, then the answer is 2 plus the number of times the direction turns (or 1 if all numbers are equal). For the first example the path turns 5 times, so 7.
• Longest alternating subarray (no skipping): walk once and reset the length whenever two steps in a row go the same way.
• Alternating by sign instead of size (positive, negative, positive): same two counter idea with signs.

Remember this

Grown-up words: the zigzag is an alternating (wiggle) subsequence, the two counters are the DP states "last step up" and "last step down", and keeping only peaks and valleys is the greedy view of the same answer.