一道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()

分up和down两列表进行dp,感觉代码很臃肿,求一个更好的实现。

Tags :

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: