C++で最長ウィグル（振動）サブシーケンスの長さを求める方法

ウィグルシーケンスとは

隣り合う数値の差が正と負で厳密に交互に現れる数列を「ウィグルシーケンス」と呼びます。最初の差は正でも負でも構いません。また、要素が2つ未満の数列は自明にウィグルシーケンスとみなされます。

例えば [1,7,4,9,2,5] はウィグルシーケンスです。隣接する数値の差が (6, -3, 5, -7, 3) となり、正と負が交互に現れているためです。一方、[1,4,7,2,5] は最初の2つの差がどちらも正であるため、[1,7,4,5,5] は最後の差が0になってしまうため、それぞれウィグルシーケンスではありません。

問題の概要

整数列が与えられたとき、ウィグルシーケンスとなっている最長の部分列（サブシーケンス）の長さを求めます。部分列とは、元の数列からいくつかの要素（0個の場合も含む）を削除し、残りの要素を元の順序のまま保ったものです。

例えば入力が [1,7,4,9,2,5] の場合、数列全体がすでにウィグルシーケンスであるため、出力は6になります。

解法のアプローチ

この問題は動的計画法（DP）の考え方を使うことで、線形時間で効率的に解けます。手順は以下の通りです。

• n を nums のサイズとします。
• n が 0 の場合は 0 を返します。
• up := 1、down := 1 と初期化します。up は「直前の差が正（上昇）で終わる最長ウィグル部分列」の長さ、down は「直前の差が負（下降）で終わる最長ウィグル部分列」の長さを表します。
• i を 1 から n-1 まで繰り返します。
  • nums[i] > nums[i-1] の場合は up := down + 1 と更新します。
  • nums[i] < nums[i-1] の場合は down := up + 1 と更新します。
• 最後に up と down の大きい方を返します。

このアルゴリズムの時間計算量は O(n)、追加のメモリ使用量は O(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