A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
def longestZigZag(testlist): size = len(testlist) up, down =  * size,  * size upprev, downprev = [-1] * size, [-1] * size for i in range(1, size): for j in range(i): if testlist[i] > testlist[j] and down[j] + 1 > up[i]: up[i], upprev[i] = down[j] + 1, j if testlist[i] < testlist[j] and up[j] + 1 > down[i]: down[i], downprev[i] = up[j] + 1, j up_maxIndex, down_maxIndex = up.index(max(up)), down.index(max(down)) if up[up_maxIndex] >= down[down_maxIndex]: maxLen, maxindex, isUpState = up[up_maxIndex], up_maxIndex, 1 else: maxLen, maxindex, isUpState = down[down_maxIndex], down_maxIndex, 0 path =  def makepath(index, isUpState): path.insert(0, testlist[index]) if isUpState: makepath(upprev[index], (isUpState+1)%2) if upprev[index] != -1 else return else: makepath(downprev[index], (isUpState+1)%2) if downprev[index] != -1 else return makepath(maxindex, isUpState) return maxLen, path #testcases mylist = [[1, 7, 4, 9, 2, 5], [1, 17, 5, 10, 13, 15, 10, 5, 16, 8], [10, 20], [20, 10], [20, 20], , [1, 2, 3, 4, 5, 6, 7, 8, 9]] for onelist in mylist: maxLen, path = longestZigZag(onelist) print maxLen print path raw_input()