https://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

ZigZag.py

class State:

    def __init__(self, longest_sequence, next_diff):
        """ next_diff = 1 means the next expected difference
        in the zigzag sequence is positive
        next_diff = 0 means the next expected difference
        in the zigzag sequence is negative """
        self.longest = longest_sequence
        self.next_diff = next_diff

    def __repr__(self):
        return "(%d, %d)" % (self.longest, self.next_diff)

class ZigZag:

    def longestZigZag(self, sequence):
        L = len(sequence)
        M = [State(0,0)] * L

        # Corner case: first 'start' numbers of the sequence are the same
        start = 1
        while sequence[start] == sequence[start-1]:
            start += 1

        # Set initial state of first unique number in sequence
        if sequence[start] > sequence[start-1]:
            M[start] = State(1, 0)
        else:
            M[start] = State(1, 1)
        start += 1

        for i in range(start, L):
            longest = 0
            next_diff = 0
            for j in range(i-1, -1, -1):
                prev_state = M[j]
                if longest > prev_state.longest:
                    break
                diff = sequence[i] - sequence[j]  # current - prev
                if prev_state.next_diff and diff > 0:
                    longest = max(longest, prev_state.longest + 1)
                    next_diff = 0
                elif not prev_state.next_diff and diff < 0:
                    longest = max(longest, prev_state.longest + 1)
                    next_diff = 1
                else:
                    longest = prev_state.longest
                    next_diff = prev_state.next_diff
            M[i] = State(longest, next_diff)

        return M[L-1].longest + 1