C++ 摆动子序列

在本文中，我们将讨论 C++ 中的摆动子序列及其算法和实现。

问题陈述

一个序列，如果相邻数字之间存在严格交替的正负差异，则称为摆动序列。第一个差异可以是正的也可以是负的。只有一个元素和两个不相等元素的序列被视为微不足道的摆动序列。

示例 1

输入：nums = [2,7,4,8,6,5]

输出：6

解释：整个序列是一个摆动序列。

示例 2

输入：nums = [1,17,5,10,13,15,10,5,17,6]

输出: 7

解释：有几个子序列达到了这个长度。

约束条件：

1 <= nums.length <= 1000

0 <= nums[i] <= 1000

概念

• 重要的一点是，任何落在同一方向的连续数字中间的数字都是不必要的。相反，更极端的数字应该保留下来，因为它们增加了后续数字指示方向改变的可能性。
• 在这种情况下，计算输入数组 (N) 中方向变化的拐点是一个直接的解决方案。有几种其他方法可以实现这一点，但是使用此函数，我们可以通过保持方向标志（向上）、增加我们的答案（ans）并在检测到变化时反转它来监控方向。
• 设置第一个方向是一项困难的任务。在第一次看到不同的数字之前，我们必须等待以确定我们的方向，因为初始数字可以指示任何方向。在主循环之前，我们可以使用一个简单的while 循环来验证这一点。
• 完成后，我们可以返回一个答案。

算法

示例

让我们举一个例子来说明 C++ 中的摆动子序列。

输出

代码解释

• 在此示例中，“wiggleMax”函数接受一个整数向量“num”作为输入，并返回最长摆动子序列的长度。
• 它初始化向量 up 和 down 以跟踪在每个索引处结束的摆动子序列的长度，其中 up[x] 表示在索引 x 处结束的序列的长度，其中最后两个元素递增，down[i] 表示在索引 x 处结束的序列的长度，其中最后两个元素递减。
• 它遍历输入数组，并根据当前值更新 up 和 down 向量。
• 如果当前元素大于前一个元素，则通过扩展递增序列来更新 up 向量，而 down 向量保持不变。
• 同样，如果当前元素较小，则通过扩展递减序列来更新 down 向量，而 up 向量保持不变。
• 如果当前元素等于前一个元素，则两个序列都保持不变。
• 最后，函数返回 up 和 down 向量的最后一个元素之间的最大长度。