## 一道dp题——ZigZag

Problem Statement:
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 = [1] * size, [1] * 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],
[44],
[1, 2, 3, 4, 5, 6, 7, 8, 9]]

for onelist in mylist:
maxLen, path = longestZigZag(onelist)
print maxLen
print path
raw_input()
```

Tags :

### One thought on “一道dp题——ZigZag”

1. EDFward说道：

试着用Racket戳了一个烂版本，http://blog.edfward.com/2013/05/rackethe-ge-xiao-dpde-gu-shi.html
顺便求黄炫圭大神速写一个不那么丑陋的…(用起来各种别扭啊…