贪心算法: 摆动序列

贪心算法在摆动序列中的应用

文章结构概述

• 贪心策略 -- 波动序列
  • • 问题再现
    • 理解题意
    • 贪心适用情境
    • 示例程序代码

题目重现

题目链接：摆动序列 - 力扣

当数字序列中相邻元素的差值在正负之间交替变化时，该序列被称为 摆动序列 。初始差值可以为正或负，但必须满足严格交替的条件。若序列仅包含一个元素或两个不相等的元素，则也被认定为摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 被视为 摆动序列 ，其相邻元素的差值 (6, -3, 5, -7, 3) 呈现出正负交替的特征。
• 相较之下，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 并不符合摆动序列的标准。前者由于前两个差值均为正值而被排除，后者则因其最后一个差值为零而无法满足要求。

子序列 指的是通过从原始数据中移除若干个（包括零个）元素后所得到的新序列，并且保留原有元素的相对顺序不变。

现在给定一个整数数组 nums ，请计算并返