All problems

Longest Turbulent Subarray

Medium · dynamic programming

A weather station logs one reading per hour, and readings[i] is the reading at hour i.

A run of consecutive readings is a zigzag if every step goes the opposite way from the step before it: up, then down, then up again, or down, then up, then down, and so on. Each step must be a real move, so two equal neighbouring readings can never sit inside a zigzag. A run of one reading is a zigzag, and a run of two readings is a zigzag when they differ.

Return the length of the longest zigzag run in readings.

Examples

Example 1

Input: readings = [9, 4, 2, 10, 7, 8, 8, 1, 9]

Output: 5

The run 4, 2, 10, 7, 8 goes down, up, down, up. The repeated 8 ends it.

Example 2

Input: readings = [4, 8, 12, 16]

Output: 2

Every step goes up, so no run longer than two can alternate.

Example 3

Input: readings = [7, 7, 7]

Output: 1

Equal neighbours are never a zigzag, so only a single reading counts.

Constraints