C++でサブシーケンスをウィグルする

連続する数の差が正と負の間で厳密に交互になる場合、ウィグルシーケンスと呼ばれる数列があるとします。最初の違いは、正または負のいずれかです。要素が2つ未満のシーケンスは、自明なウィグルシーケンスです。したがって、たとえば、[1,7,4,9,2,5]は小刻みに動くシーケンスです。これは、表示されている場合、差（6、-3,5、-7,3）が交互に正と負であるためです。ただし、[1,4,7,2,5]と[1,7,4,5,5]はウィグルシーケンスではありません。最初のシーケンスは、最初の2つの差が正であるため、2番目のシーケンスは最後の差がゼロであるためです。 。

したがって、整数のシーケンスがあり、ウィグルシーケンスである最長のサブシーケンスの長さを見つける必要があります。サブシーケンスは、元のシーケンスからいくつかの要素（最終的にはゼロ）を削除し、残りの要素を元の順序のままにしておくことで取得されます。したがって、入力が[1,7,4,9,2,5]の場合、シーケンス全体がウィグルシーケンスであるため、出力は6になります。

これを解決するには、次の手順に従います-

• n：=numsのサイズ

• nが0の場合、0を返します

• セットアップ：=1およびダウン：=1

• 1からn–1の範囲のiの場合

  • nums [i]> nums [i – 1]の場合、up：=down + 1

  • それ以外の場合、nums [i]

• 上下の最大値を返す

例（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