Find the longest zigzag sequence in a array of integers
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