Zigzag border

A pen plotter draws a decorative border from a list of anchor heights. A border only reads as a zigzag if every stroke reverses the one before it.

The problem

The design file gives the pen's anchor heights in draw order. The plotter may drop anchors — it draws a straight stroke from each kept anchor to the next kept one, in file order — but it may not reorder them.

A border is a zigzag when the strokes strictly alternate: up, down, up, down, or down, up, down, up. A stroke of zero height is not a direction, so two equal anchors can never sit next to each other in the kept list. Report the number of anchors on the longest zigzag that can be kept. A single anchor counts as a zigzag of length 1, and an empty file gives 0.

Input. anchors — a list of integers, the pen height at each anchor in draw order.

Output. The number of anchors in the longest zigzag subsequence.

Example.

anchors = [40, 40, 55, 20, 20, 35, 30]   ->  5

Keeping 40, 55, 20, 35, 30 gives strokes +15, -35, +15, -5 — four strokes that alternate. The repeated 40 and 20 have to go; a flat stroke breaks the run.

A second example, where the file only climbs:

anchors = [5, 9, 14, 20]   ->  2

Every stroke is upward, so at most one of them survives — the border is a single line from any anchor to a higher later one.

Constraints.

• 0 <= len(anchors) <= 10^4
• 0 <= anchors[i] <= 10^4

Hints

Approach

Brute force

Try every subsequence and check whether its strokes alternate: 2ⁿ subsets, which at 10⁴ anchors is not a number worth writing down. Even memoising on (position, direction of the last stroke) still walks every earlier anchor as a candidate predecessor, at O(n²).

The insight

Only two numbers matter: the longest zigzag ending with an up stroke and the longest ending with a down stroke — and each anchor updates exactly one of them.

If the current anchor is higher than the one before it in the file, the best border ending on an up stroke becomes down + 1: any zigzag that ended going down can be extended, and using the immediately preceding anchor is never worse than an earlier one, because a longer up-run's peak is always reachable. If it is lower, down becomes up + 1. If the two are equal, neither counter moves — a flat stroke carries no direction. That makes the scan linear with two variables and no table at all.

Algorithm

1. If the file is empty, return 0.
2. Set up = down = 1.
3. Walk the anchors from the second onward, comparing each with its file predecessor.
4. If it is higher, set up = down + 1. If it is lower, set down = up + 1. If equal, change nothing.
5. Return max(up, down).

Complexity

Time O(n) — one comparison per anchor. Space O(1); the two counters are the entire state.

Solution

"""Zigzag border — longest alternating subsequence, held in two rolling counters."""


def solve(anchors):
    if not anchors:
        return 0
    # up   = anchors on the best zigzag so far whose last stroke went upward.
    # down = the same for a last stroke that went downward.
    # A flat stroke has no direction, so it moves neither.
    up = down = 1
    for previous, current in zip(anchors, anchors[1:]):
        if current > previous:
            up = down + 1        # an up stroke extends a border that ended down
        elif current < previous:
            down = up + 1
    return max(up, down)

TESTS = [
    (([40, 40, 55, 20, 20, 35, 30],), 5),
    (([5, 9, 14, 20],), 2),
    (([8, 8, 8, 8],), 1),
    (([],), 0),
    (([17],), 1),
    (([3, 9, 4, 11, 6],), 5),
    (([20, 5],), 2),
]

Pitfalls

• Updating both counters from the same step's values. Writing up = down + 1 and then down = up + 1 in one branch double-counts the stroke; only one direction may move per anchor.
• Treating equal neighbours as a rise. A file of [8, 8, 8, 8] then reports 4, when the plotter has drawn a single flat line and the answer is 1.
• Seeding the counters at 0. A one-anchor file returns 0 instead of 1; the first anchor is already a zigzag with no strokes.
• Comparing against the last kept anchor rather than the file predecessor. Bookkeeping the kept list is unnecessary here, and getting it wrong loses the peak of a long climb.

Variants

• The rising traverse — the same "pick a subsequence in order" question with a monotone condition, which needs a table and an O(n²) scan.
• Linear DP — the general recipe for rolling a table down to a fixed number of variables.