Find the longest zigzag sequence in a array of integers I think I have a brute force solution to the problem but I can't think of a more optimal solution

A sequence of integers is called a zigzag sequence if each of its elements is either strictly less than both neighbors or strictly greater than both neighbors. For example, the sequence 4 2 3 1 5 3 is a zigzag, but 7 3 5 5 2 and 3 8 6 4 5 aren't.
For a given array of integers return the length of its longest contiguous sub-array that is a zigzag sequence.

Example

For a = [9, 8, 8, 5, 3, 5, 3, 2, 8, 6], the output should be
zigzag(a) = 4.

The longest zigzag sub-arrays are [5, 3, 5, 3] and [3, 2, 8, 6] and they both have length 4.

Input/Output
[input] array.integer a  

constraints:
2 ≤ a.length ≤ 25,
0 ≤ a[i] ≤ 100.

Here is my brute force solution

def zigzag(input):
    current_longest = 0
    longest_subset  = []
    input_length    = len(input)

    for x in range(input_length):
        current_list = input[x:]

        for pos_a, num_a in enumerate(current_list):
            subset      = [num_a, ]
            prev_trend  = None

            for pos_b, num_b in enumerate(current_list[pos_a + 1:]):
                last_number = subset[-1]

                if last_number == num_b:
                    # print "[DUPE] current subset state", subset, "comparing -&gt;", subset[-1], num_b
                    break

                if last_number &gt; num_b:
                    cur_trending = "down"
                else:
                    cur_trending = "up"

                if prev_trend:
                    # compare trends
                    if prev_trend == cur_trending:
                        # print "[TREND] current subset state", subset, "comparing -&gt;", subset[-1], num_b
                        break
                    else:
                        prev_trend = cur_trending
                else:
                    # initial trend set
                    prev_trend = cur_trending

                subset.append(num_b)

                if len(subset) &gt; current_longest:
                    current_longest = len(subset)
                    longest_subset = subset

    print current_longest, longest_subset

zigzag([9, 8, 8, 5, 3, 5, 3, 2, 8, 6])
zigzag([4, 2, 3, 1, 5, 3])
You can do this in \$O(n)\$ rather than \$O(n^3)\$. To force this, change input to an iterator. I'd also make a function that returns all the zigzags, so for [9, 8, 8, 5, 3, 5, 3, 2, 8, 6] it'd return [(9, 8), (8,), (8, 5), (5, 3, 5, 3), (3, 2, 8, 6)].

The reason you'd want to do this, is as you can then make zigzag a three line function, and you know that you're building actual zigzags of the maximum size.

There's a fairly simple algorithm that you can follow to build the zigzags:


Go through the input.
If two adjacent items are the same, yield the current zigzag, and a new zigzag only containing that duplicate item.
If three adjacent items don't zigzag, yield the current zigzag, and start a new zigzag starting at the second item.


In more depth, I achieved this by doing:


Build a stack, and add the first number to it.
Loop until you run out of items in input:


Force the stack to be a size of two. If it contains three items, only keep the last two. If it has one item, add an item from the input to it.
If the first item in the stack, is the same as the second item in the stack, yield the first item, and make a stack that only contains the second item. Restart the loop.
Store the direction of the zigzag. (find if item 1 > item 2 for example.)
Infinitely do:


Copy the previous item from the stack.
Get a new item from the input.
If the previous or current item are the same, or they are the same direction as the previous zigzag, then stop looping.
Add the current item to the stack.
Store the current state of the zigzag.

yield the stack as a tuple. (Don't want people mutating the data.)
Add the current item to the stack.

If the stack has been initialized and contains items, yield the stack as a tuple.


Which can be implemented as:

def zigzags(input):
    input = iter(input)
    stack = None
    try:
        stack = [next(input)]
        while True:
            if len(stack) &lt; 2:
                stack.append(next(input))
            else:
                stack = stack[-2:]
            a, b = stack
            if a == b:
                yield (a,)
                stack = [b]
                continue
            zig = a &gt; b
            while True:
                prev = stack[-1]
                this = next(input)
                if prev == this or zig == (prev &gt; this):
                    break
                stack.append(this)
                zig = not zig
            yield tuple(stack)
            stack.append(this)
    except StopIteration:
        pass
    if stack:
        yield tuple(stack)

def zigzag(input):
    item = max(zigzags(input), key=len)
    print len(item), item