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

この記事では、n個の整数からなる配列 arr[] が与えられたとき、指定された条件を満たす部分配列（サブ配列）の最大サイズを求めるプログラムを C++ で作成する方法を解説します。

問題の概要

目的は、以下のいずれかの条件を満たす最長の部分配列の長さを求めることです。

• k が奇数のとき arr[k] > arr[k+1]、k が偶数のとき arr[k] < arr[k+1] が成立すること（部分配列のすべての要素に対して）
• k が奇数のとき arr[k] < arr[k+1]、k が偶数のとき arr[k] > arr[k+1] が成立すること（部分配列のすべての要素に対して）

ここで k とは、部分配列の各要素が元の配列 arr[] 内で持つインデックスのことです。

入出力例

具体例を使って問題を確認しましょう。

入力

arr[] = {7, 3, 1, 5, 4, 2, 9}

出力

4

解説

部分配列 {3, 1, 5, 4} が条件1を満たします。
k = 1（奇数）: arr[k] > arr[k+1] → 3 > 1
k = 2（偶数）: arr[k] < arr[k+1] → 1 < 5
k = 3（奇数）: arr[k] > arr[k+1] → 5 > 4

解決アプローチ

この例から分かるように、いずれかの条件が成立するためには、部分配列の要素が大小交互に並んでいる必要があります。つまり、1番目が2番目より大きければ、次は2番目が3番目より小さい、さらにその次は逆になる、という具合に大小関係が入れ替わっていくイメージです。

そこで計算を容易にするため、隣接要素間の大小関係を表す「関係配列（relArr）」を作成します。関係配列は次のように構築します。

arr[i] == arr[i + 1] の場合 … relArr[i] = 'E'
arr[i] > arr[i + 1] の場合 … relArr[i] = 'G'
arr[i] < arr[i + 1] の場合 … relArr[i] = 'S'

この配列を利用すれば、最大部分配列のサイズを簡単に求められます。候補となる部分配列は、'G' と 'S' が交互に並んでいる区間です。

C++実装例

上記の解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

// 2つの値の大小関係を判定する
char findRel(int a, int b) {
    if (a > b)
        return 'G';
    else if (a < b)
        return 'S';
    return 'E';
}

int calcMaxSubArray(int arr[], int n) {
    int maxLen = 1;
    int len = 1;
    char c = findRel(arr[0], arr[1]);
    for (int i = 1; i < n - 1; i++) {
        if (c == 'S' && findRel(arr[i], arr[i + 1]) == 'G')
            len++;
        else if (c == 'G' && findRel(arr[i], arr[i + 1]) == 'S')
            len++;
        else {
            if (maxLen < (len + 1))
                maxLen = (len + 1);
            len = 1;
        }
        c = findRel(arr[i], arr[i + 1]);
    }
    // 配列の末尾まで続いた部分配列も考慮する
    if (maxLen < (len + 1))
        maxLen = (len + 1);
    return maxLen;
}

int main() {
    int arr[] = {7, 3, 1, 5, 4, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "指定された条件を満たす部分配列の最大サイズは "
         << calcMaxSubArray(arr, n);
}

実行結果

指定された条件を満たす部分配列の最大サイズは 4

計算量の評価

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(n)、追加で必要なメモリは O(1) と非常に効率的です。また、関係配列を実際にメモリ上へ展開せず、findRel 関数でその都度判定する方式を採用している点も省メモリのポイントです。