# 贪心算法-最长摇摆序列

如图最长摇摆序列被计算为7：

![](/files/-LokoTBQVgBuaR8AqEm9)

`PS：贪心计算未必正确`

```python
'''
一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列被称为摇摆序列。
一个小于2个元素的序列直接为摇摆序列。
例如:
序列 [1, 7, 4, 9, 2, 5]，相邻元素的差 (6, -3, 5, -7, 3)，该序列为摇摆序列。
序列 [1,4,7,2,5] (3, 3, -5, 3)、 [1,7,4,5,5] (6, -3, 1, 0)不是摇摆序列。
给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度。
例如: 输入[1,7,4,9,2,5]，结果为6;
输入[1,17,5,10,13,15,10,5,16,8]，结果为7([1,17,10,13,10,16,8] );
输入[1,2,3,4,5,6,7,8,9]，结果为2。

'''

def max_wiggle_len(nums):
    max_l = 1
    if len(nums) <= 2:
        return len(nums)
    state = 0  # 0 start,1 up,2 down

    for i in range(1, len(nums)):
        if state == 0:  # 上一步留在start状态，怎样都摇摆，除非 值一样
            if nums[i] > nums[i - 1]:  # up
                state = 1
                max_l += 1
                print(nums[i - 1], '⬆', nums[i])
                continue
            if nums[i] < nums[i - 1]:  # down
                state = 2
                max_l += 1
                print(nums[i - 1], '⬇', nums[i])
                continue
        if state == 1:  # 上一步留在up状态，需要下降
            if nums[i] < nums[i - 1]:  # down
                state = 2
                max_l += 1
                print(nums[i - 1], '⬇', nums[i])
                continue

        if state == 2:  # 上一步留在down状态，需要上升
            if nums[i] > nums[i - 1]:  # up
                state = 1
                max_l += 1
                print(nums[i - 1], '⬆', nums[i])
                continue
    return max_l


if __name__ == '__main__':
    nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
    l = max_wiggle_len(nums)
    print(l)

'''
1 ⬆ 17
17 ⬇ 5
5 ⬆ 10
15 ⬇ 10
5 ⬆ 16
16 ⬇ 8
7
'''
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/si-xiang-lei/tan-xin/zui-chang-yao-bai-xu-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.