ZigZag - 2003 TCCC Semifinals 3 http://community.topcoder.com/tc?module=ProblemDetail&rd=4493&pm=1259

dp_2.py

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

def longest_zigzag(A):
    n = len(A)
    d = [0] * n
    s = [0] * n
    last_indices = [0] * n
    longest_len = 1

    for i in range(0, n):
        d[i] = 1
        for j in range(0, i):
            if not A[i] == A[j]:
                cmp = 1 if A[i] > A[j] else -1
                if cmp != s[j]:
                    s[i] = cmp
                    d[i] = d[j] + 1
                    last_indices[i] = j
        if d[i] > longest_len:
            longest_len = d[i]

    return (d, s, last_indices, longest_len)

def find_subsequence(A, d, last_indices):
    start_pos = d.index(sorted(d)[-1])
    longest_subsequence = []

    def find(A, last_indices, start_pos, lis):
        num = A[start_pos]
        lis.insert(0, num)

        new_pos = last_indices[start_pos]

        if new_pos != start_pos:
            find(A, last_indices, new_pos, lis)
        else:
            return lis

    find(A, last_indices, start_pos, longest_subsequence)
    return longest_subsequence


if __name__ == '__main__':
    # A = [1, 7, 4, 9, 2, 5]
    # A = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
    # A = [44]
    # A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # A = [70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32]
    A = [374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
         600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
         67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
         477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
         249, 22, 176, 279, 23, 22, 617, 462, 459, 244]

    (d, s, last_indices, length) = longest_zigzag(A)
    print(A)
    print('=' * 10)

    # print(d)
    # print(s)
    # print('=' * 10)

    print(length)
    print('=' * 10)

    # print(last_indices)
    print(find_subsequence(A, d, last_indices))