ジグザグ数 zigzag

f:id:peroon:20190728211056j:plain

1 2 1 2 1 => 5
  • となるような関数を作った。再利用することがあるかも
  • ジグザグ数と名付けた
  • 冗長に書いてある

使用例 (to verify)

Code

// 1 2 1 2 1 => 5
ll zigzag(vector<ll>& A){
    // イコール除去
    vector<ll> B;
    B.push_back(A[0]);
    ll prev = A[0];
    FOR(i, 1, A.size()){
        if(A[i]!=prev){
            B.push_back(A[i]);
            prev = A[i];
        }
    }
    if(B.size()==1){
        return 1;
    }

    ll tilt;
    if(B[0]<B[1]){
        tilt = 1;
    }else{
        tilt = -1;
    }
    ll count = 1; // 始点
    ll current = B[1];
    FOR(i, 2, B.size()){
        if(current<B[i]){
            if(tilt==1){
                //
            }else if(tilt==-1){
                // 折れ
                count++;
                tilt = 1;
            }
        }
        // 今回下がる
        else if(current>B[i]){
            if(tilt==1){
                // 折れた
                count++;
                tilt = -1;
            }
            else if(tilt==-1){
                //
            }

        }
        current = B[i];
    }
    return count+1; // 終点を足す
}