C ++中的摆动子序列

假设我们有一个数字序列，如果连续数字之间的差严格在正负之间交替，则称为摆动序列。第一差异可以是正的或负的。少于两个元素的序列通常是摆动序列。因此，例如[1,7,4,9,2,5]是一个摆动序列，因为如果您看到的话，差异(6,-3,5,-7,3)交替为正和负。但是，[1,4,7,2,5]和[1,7,4,5,5]不是摆动序列，第一个是因为其前两个差为正，第二个是因为其最后差为零。

因此，我们有一个整数序列，我们必须找到最长的子序列即摆动序列的长度。通过从原始序列中删除一些元素（最终也为零）来获得子序列，而其余元素保持其原始顺序。因此，如果输入类似于[1,7,4,9,2,5]，则输出将为6。因为整个序列是一个摆动序列。

为了解决这个问题，我们将遵循以下步骤-

• n：= nums的大小

• 如果n为0，则返回0

• 设置：= 1和向下：= 1

• 当我在1到n – 1的范围内时

• 如果nums [i]> nums [i – 1]，则向上：=向下+ 1

• 否则，当nums [i] <nums [i – 1]时，则向下：=向上+ 1

• 返回最大上下

范例（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int wiggleMaxLength(vector<int>& nums) {
      int n = nums.size();
      if(!n) return 0;
      int up = 1;
      int down = 1;
      for(int i = 1; i < n; i++){
         if(nums[i] > nums[i - 1]){
            up = down + 1;
         }
         else if(nums[i] < nums[i - 1]){
            down = up + 1;
         }
      }
      return max(up, down);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,7,4,9,2,5};
   cout << (ob.wiggleMaxLength(v));
}

输入项

[1,7,4,9,2,5]

输出结果

6