topcoder: ZigZag

再来水一道简单题：题目地址

想法很自然，记录下当前的方向，一旦出现方向不一致的就把总数加一，同时方向改变，否则continue，然而其实已经包含了动态规划思想

上代码：

class ZigZag:
    def longestZigZag(self, seq):
        count = 1
        d = 0
        p = seq[0]
        for i in seq[1:]:
            if p == i:
                continue
            elif p < i:
                if d == 1:
                    p = i
                    continue
                else:
                    count += 1
                d = 1
            else:
                if d == -1:
                    p = i
                    continue
                else:
                    count += 1
                d = -1
            p = i

        return count

看了下别人提交的，思路一样，只不过有人上来先把整个序列的变化趋势算一遍，即遍历seq，然后算出seq[i]-seq[i-1]的值记录下来记为V[i]，其实要的就是一个正负号，然后再次遍历还是记录当前的方向，乘以当前遍历到的那个趋势V[i]，乘积发生变化时就在结果上加一并改变当前方向值。