【C++】特定の要素を除外した最大部分配列和の求め方を実装付きで解説

はじめに

このチュートリアルでは、特定の要素を除外した状態で最大となる部分配列和(Maximum Subarray Sum)を求めるプログラムを、C++で実装する方法を解説します。

ここで扱う問題は次の通りです。サイズNの配列Aと、サイズMの配列Bが与えられます。このとき、「部分配列内のどの要素も配列Bに含まれていない」という条件を満たす配列Aの部分配列の中から、要素の合計が最大になるものを見つけてください。

アルゴリズムの考え方

この問題は、最大連続部分配列和を求める有名なKadane(カダネ)のアルゴリズムを応用することで効率よく解けます。手順は以下の通りです。

1. 配列Aを先頭から順に走査します。
2. 現在の要素が配列Bに含まれている場合、その要素を含む部分配列は条件違反となるため、それまでの連続和(curr_max)を0にリセットします。
3. 含まれていない場合は、通常のKadaneのアルゴリズムと同様に「現在の要素から新しく始める」か「これまでの連続和に加算する」かの大きい方を採用し、全体の最大値(max_so_far)を更新します。

C++での実装例

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

// 対象の要素が2番目の配列に存在するかどうかを判定する
bool isPresent(int B[], int m, int x) {
    for (int i = 0; i < m; i++)
        if (B[i] == x)
            return true;
    return false;
}

int findMaxSubarraySumUtil(int A[], int B[], int n, int m) {
    int max_so_far = INT_MIN, curr_max = 0;
    for (int i = 0; i < n; i++) {
        // 除外対象の要素なら連続和をリセット
        if (isPresent(B, m, A[i])) {
            curr_max = 0;
            continue;
        }
        curr_max = max(A[i], curr_max + A[i]);
        max_so_far = max(max_so_far, curr_max);
    }
    return max_so_far;
}

void findMaxSubarraySum(int A[], int B[], int n, int m) {
    int maxSubarraySum = findMaxSubarraySumUtil(A, B, n, m);
    if (maxSubarraySum == INT_MIN) {
        cout << "Maximum Subarray Sum cant be found" << endl;
    } else {
        cout << "The Maximum Subarray Sum = " << maxSubarraySum << endl;
    }
}

int main() {
    int A[] = { 3, 4, 5, -4, 6 };
    int B[] = { 1, 8, 5 };
    int n = sizeof(A) / sizeof(A[0]);
    int m = sizeof(B) / sizeof(B[0]);
    findMaxSubarraySum(A, B, n, m);
    return 0;
}

実行結果

The Maximum Subarray Sum = 7

コードの解説

isPresent関数:ある要素xが配列Bの中に存在するかどうかを線形探索で判定します。1回の呼び出しにかかる時間計算量はO(M)です。

findMaxSubarraySumUtil関数:アルゴリズムの中心となる関数です。除外対象の要素に出会った時点で連続和をリセットし、それ以外の要素に対してはKadaneのアルゴリズムで最大連続和を更新していきます。

findMaxSubarraySum関数:計算結果を受け取って出力するラッパー関数です。すべての要素が除外対象となり有効な部分配列が存在しない場合は、max_so_farがINT_MINのままのため、その旨のメッセージを表示します。

実行結果の検証

サンプルでは配列A = {3, 4, 5, -4, 6}、配列B = {1, 8, 5}を使用しています。要素5が除外対象のため、配列Aは要素5を境界として{3, 4}と{-4, 6}の2つの区間に分かれます。それぞれの合計は7と2であり、最大値である7が出力されます。

計算量と改善のヒント

上記の実装では、配列Aの各要素について配列Bとの照合を行うため、時間計算量はO(N×M)となります。配列Bの要素を事前にunordered_set(ハッシュセット)へ格納しておけば、存在判定を平均O(1)で行えるため、全体の計算量をO(N+M)まで改善できます。大規模な入力を扱う場合はこちらの方法を検討するとよいでしょう。