C++で指定された条件を満たす部分配列の最大サイズを求める方法

はじめに

このチュートリアルでは、指定された条件を満たす部分配列(サブ配列)の最大サイズを求めるC++プログラムについて解説します。この問題は、隣接する要素同士の大小関係が交互に入れ替わる「ジグザグ(乱流)パターン」を持つ、最長の連続区間を見つけるというものです。

問題の定義

整数型の配列が与えられたとき、次のいずれかの条件を満たす最長の部分配列を求めます。

• 条件A: kが奇数のとき arr[k] > arr[k+1]、kが偶数のとき arr[k] < arr[k+1]
• 条件B: kが偶数のとき arr[k] > arr[k+1]、kが奇数のとき arr[k] < arr[k+1]

つまり、隣接する要素の比較結果(大きい・小さい)が毎回反転し、値が等しくなる箇所がないような連続した区間の中で、最も長いものの長さを答える問題です。

アルゴリズムの考え方

この問題は「アンカー(基準点)」を使ったスライディングウィンドウ的なアプローチで効率よく解けます。

1. 隣接する2つの要素を比較し、その結果を +1(左が大)、-1(右が大)、0(等しい)として記録します。
2. 比較結果の符号が連続して反転している間は、同じジグザグ区間が続いています。
3. 符号が反転しなくなったタイミング、または配列の末尾に達したタイミングで、アンカーから現在位置までの長さを候補として記録し、アンカーを更新します。
4. 隣接する値が等しい場合はパターンが途切れるため、アンカーをその位置に移動します。

この方法なら配列を一度走査するだけでよく、時間計算量は O(n)、空間計算量は O(1) に抑えられます。

サンプルコード

#include<bits/stdc++.h>
using namespace std;

// a と b を比較する(a > b なら 1、a < b なら -1、等しければ 0)
int cmp(int a, int b) {
    return (a > b) - (a < b);
}

// 条件を満たす最長の部分配列の長さを返す
int maxSubarraySize(int arr[], int n) {
    int ans = 1;
    int anchor = 0;
    for (int i = 1; i < n; i++) {
        int c = cmp(arr[i - 1], arr[i]);
        if (c == 0)
            anchor = i; // 値が等しくパターンが途切れる
        else if (i == n - 1 || c * cmp(arr[i], arr[i + 1]) != -1) {
            // 符号の反転が終わった、または末尾に到達した
            ans = max(ans, i - anchor + 1);
            anchor = i;
        }
    }
    return ans;
}

int main() {
    int arr[] = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSubarraySize(arr, n);
}

コードの解説

• cmp 関数は2つの整数を比較し、a の方が大きければ 1、小さければ -1、等しければ 0 を返します。
• maxSubarraySize 関数では、変数 anchor が現在調べている区間の起点を表します。
• 隣接要素の比較結果 c と次の比較結果の積が -1 にならない(= 大小関係が反転しない)とき、そこが区間の終端なので長さを確定します。
• 値が等しい(c == 0)場合はパターンが崩れるため、アンカーをその位置へ移動させます。

実行結果

6

入力配列 {9, 4, 2, 10, 7, 8, 8, 1, 9} の場合、「9 > 4 > 2 < 10 > 7 < 8」というように大小関係が交互に入れ替わる区間が最も長く、その長さは 6 になります。なお、途中の「8, 8」のように隣接する値が等しくなると条件を満たさなくなり、そこで区間が分断される点に注意してください。

まとめ

本記事では、隣接要素の大小関係が交互に入れ替わる条件を満たす最長部分配列を、アンカー方式の線形走査で求める方法を紹介しました。配列を1回走査するだけで済むため、大きな入力に対しても高速に動作します。ぜひ自分の環境でコードを実行して、挙動を確認してみてください。