Zigzag subarray

You are given an array of integers. Write a script to find the length of the longest contiguous subarray where the numbers alternate between strictly increasing and strictly decreasing (a ZigZag pattern).

A sequence of numbers $A = [a0, a1, …, ak]$ with length $k >= 1 is considered a ZigZag sequence if every adjacent pair alternates direction:

• a_0 < a_1 > a_2 < a_3 > ...
• OR
• a_0 > a_1 < a_2 > a_3 < ...

NOTE: A single element (length 1) or any two distinct elements (length 2) are automatically valid ZigZag sequences. Equal adjacent numbers (e.g., 5, 5) break the pattern.

Examples

Example 1
Input: @nums = (9, 4, 2, 10, 7, 8, 8, 1, 9)
Output: 5
ZigZag subarray: (4, 2, 10, 7, 8)

Example 2
Input: @nums = (1, 7, 4, 9, 2, 5)
Output: 6
ZigZag subarray: (1, 7, 4, 9, 2, 5)

Example 3
Input: @nums = (1, 2, 3, 4, 5)
Output: 2
ZigZag subarray: (1, 2)

Example 4
Input: @nums = (4, 4, 4)
Output: 1

Example 5
Input: @nums = (10, 20, 15, 12, 18)
Output: 3
ZigZag subarray: (10, 20, 15)

Analysis

This is another good example where the human eye and brain can easily spot the longest sequence, but procedural language finds it harder.

I start by creating a string, which lists the relationship between each array element and the following one using U (for 'up') if the second element exceeds the first, D (for 'down') if the first exceeds the second, and E (for 'equal') if they are the same.

I then search successively for any of the following patterns:

D[UD]*, [UD]*U, [UD]* [DU]*

If any of these match, then the desired output is simply the length of the match plus 1. For example, UDUDU derives from a sequence of 6 zig-zagged numbers such as 1, 2, 1, 2, 1, 2. I do this search starting from the largest possible match and then decreasing, so that the first successful match is the best.

I think, though I haven't tried it, that this could all be done in a single regex using nested parentheses and back references within the match, but it would be hard to understand or maintain.

It is probably the case that a solution involving a single pass along the array would be faster, but my solution handles an array of 10000 random integers in the range 0..1000 in a few seconds.

Try it 

Your input:

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/389/2

use v5.26;    # The Weekly Challenge - 2026-08-31
use utf8;     # Week 389 - task 2 - Zigzag subarray
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

zigzag_subarray(9, 4, 2, 10, 7, 8, 8, 1, 9);
zigzag_subarray(1, 7, 4, 9, 2, 5);
zigzag_subarray(1, 2, 3, 4, 5);
zigzag_subarray(4, 4, 4);
zigzag_subarray(10, 20, 15, 12, 18);
zigzag_subarray(7, 7);
zigzag_subarray(6);
zigzag_subarray(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);

sub zigzag_subarray {
    
    my (@array, $p, $string, $test, $best, $k);
    
    # initialise
    @array = @_;
    say qq[\nInput:  (] . join(', ', @array) . ')';
    $test = '';
    $string = '';

    # make string of U = up, D = down, E = equal pairs
    for $p (0 .. $#array - 1) {
        $string .= $array[$p + 1] > $array[$p] ? 'U' :
            ($array[$p + 1] < $array[$p] ? 'D' : 'E');
    }

    # check for largest [UD]*U, D[UD]*, [UD]*, [DU]*
    P: for ($p = int(@array / 2); $p >= 0; $p --) {
        for $k (1 .. 4) {
            if    ($k == 1) { $test = 'UD' x $p . 'U' }
            elsif ($k == 2) { $test = 'D' . 'UD' x $p }
            elsif ($k == 3) { $test = 'UD' x $p }
            elsif ($k == 4) { $test = 'DU' x $p }
            if ($string =~ m|$test|) {
                say qq[Output: ] . (length($test) + 1);
                return;
            }
        }
    }
}

18 lines of code
Completed after the closing date and not submitted to GitHub

Output from script

Input:  (9, 4, 2, 10, 7, 8, 8, 1, 9)
Output: 5

Input:  (1, 7, 4, 9, 2, 5)
Output: 6

Input:  (1, 2, 3, 4, 5)
Output: 2

Input:  (4, 4, 4)
Output: 1

Input:  (10, 20, 15, 12, 18)
Output: 3

Input:  (7, 7)
Output: 1

Input:  (6)
Output: 1

Input:  (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5)
Output: 5