C++で最大要素がkとなる重複しない部分配列の長さの最大合計を求める方法

問題概要

この問題では、整数型の配列と整数 k が与えられます。求めるのは、「最大要素がちょうど k となる重複しない（オーバーラップしない）部分配列」について、その長さの合計の最大値です。

言い換えると、与えられた配列から切り出せる連続した部分配列のうち、最大値が k と一致するものだけを選び、それらが互いに重ならないようにした場合の長さの総和を最大化する、という問題です。

問題の詳細

入力として配列と整数 k を受け取り、配列内から作成可能なすべての部分配列のうち、最大要素が k になるものを探します。そして、互いに重複しないような部分配列を選んだときの長さの合計を求めます。

具体例で理解しよう

入力: array = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5}、k = 3

出力: 7

説明: 最大要素が 3 となる重複しない部分配列は以下の通りです。

{3} : 長さ = 1
{1, 2, 3, 1} : 長さ = 4
{3, 2} : 長さ = 2
長さの合計 = 1 + 4 + 2 = 7

注目すべきは、要素 7 や 6 のように k より大きい値が含まれる区間は候補から除外されるという点です。これにより、配列は「k 以下の要素が連続する区間」に分割され、それぞれの区間に k が含まれている場合のみ、その区間の長さを合計に加算できます。

解法のアプローチ

この問題は、配列を一度だけ走査する線形時間（O(n)）のアルゴリズムで解くことができます。

アルゴリズムの手順

1. 配列を先頭から順に走査し、現在の要素が k 以下である限り、部分配列の長さをカウントしていきます。
2. 走査中に要素が k と一致したら、フラグを立てます。
3. k 以下の連続区間が終わった時点で、フラグが立っていれば（＝その区間に k が含まれていれば）、区間の長さを合計に加算します。
4. k より大きい要素はスキップし、次の区間へ進みます。
5. 配列の末尾まで繰り返し、最終的な合計を返します。

C++での実装例

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

#include <iostream>
using namespace std;

int subArrayLengthSum(int arr[], int n, int k){
    int lengthSum = 0;      // 長さの合計
    int subarrayLength = 0; // 現在の部分配列の長さ
    int flag = 0;           // 区間内に k が存在するかのフラグ

    for (int i = 0; i < n;) {
        subarrayLength = 0;
        flag = 0;
        // k 以下の要素が続く限り区間を伸ばす
        while (arr[i] <= k && i < n) {
            subarrayLength++;
            if (arr[i] == k)
                flag = 1;
            i++;
        }
        // 区間に k が含まれていれば長さを加算
        if (flag == 1)
            lengthSum += subarrayLength;
        // k より大きい要素はスキップ
        while (arr[i] > k && i < n)
            i++;
    }
    return lengthSum;
}

int main(){
    int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int ans = subArrayLengthSum(arr, size, k);
    cout<<"最大要素が "<<k<<" である重複しない部分配列の長さの最大合計は "<<ans;
    return 0;
}

実行結果

最大要素が 3 である重複しない部分配列の長さの最大合計は 7

計算量

時間計算量: O(n) — 配列を一度だけ走査するため、要素数 n に対して線形時間で処理が完了します。

空間計算量: O(1) — 追加のデータ構造を使用せず、定数個の変数のみで処理できます。

まとめ

最大要素が k となる重複しない部分配列の長さの合計を求める問題は、「k 以下の要素の連続区間ごとに配列を分割し、k を含む区間のみ長さを加算する」というシンプルな発想で解決できます。単一パスの走査で完結するため、大規模な入力にも対応できる効率的なアルゴリズムです。