C++で特定の要素を除外した最大部分配列の和を求める方法

この問題では、サイズ n の配列 arr1[] と、サイズ m の配列 arr2[] の2つが与えられます。私たちのタスクは、arr2[] に含まれる要素を除外した状態で、arr1[] の最大部分配列の和（Maximum Subarray Sum）を求めるプログラムを作成することです。

問題の概要

配列 arr1[] の要素のうち、arr2[] に存在しない要素のみを使って、連続する部分配列の和が最大になるものを見つける必要があります。

入力例

arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}

出力例

9

解説

arr1[] から arr2[] の要素 {7, 2, 9} を取り除くと、残るのは {4, 5} です。これらは連続した部分配列を構成するため、和は 4 + 5 = 9 となります。

解法アプローチ：改良版カダネのアルゴリズム

この問題に対する基本的なアプローチは、カダネのアルゴリズム（Kadane's Algorithm）を応用することです。通常のカダネのアルゴリズムは、配列内の正の連続シーケンス（部分配列）を効率的に見つけ、その和の最大値を返すことで知られています。

今回の問題では、arr2[] に含まれる要素を最大部分配列の候補から除外する必要があります。そこで、各要素について arr2[] 内に存在するかどうかを検索し、存在する場合は現在のウィンドウ（累積和）をリセットして新たな部分配列の探索を開始します。そして、現在の和が maxSum より大きければ maxSum を更新していきます。

実装例（二分探索版）

以下のプログラムは、二分探索を使って arr2[] 内の要素の有無を確認しながら、改良版カダネのアルゴリズムを実装したものです。

#include <iostream>
using namespace std;

// 二分探索により arr2[] 内に searchEle が存在するか判定
int isInArr2(int arr2[], int start, int end, int searchEle){
    if (end >= start) {
        int mid = start + (end − start) / 2;
        if (arr2[mid] == searchEle)
            return true;
        if (arr2[mid] > searchEle)
            return isInArr2(arr2, start, mid − 1, searchEle);
        return isInArr2(arr2, mid + 1, end, searchEle);
    }
    return false;
}

// 特定の要素を除外した最大部分配列の和を計算
int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
    int maxSum = −1, sum = 0;
    for (int i = 0; i < n; i++) {
        // arr2[] に含まれる要素なら、ここで部分配列を区切る
        if (isInArr2(arr2, 0, m, arr1[i])) {
            sum = 0;
            continue;
        }
        sum = max(arr1[i], sum + arr1[i]);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main(){
    int arr1[] = { 5, 4, 7, 2, 9 };
    int arr2[] = { 1, 9, 2, 7 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
    cout<<"The maximum Subarray Sum Excluding Certain Elements is "
       <<calcMaxSubArraySum(arr1, arr2, n, m);
    return 0;
}

出力

The maximum Subarray Sum Excluding Certain Elements is 9

より効率的なアプローチ：ハッシュマップによる高速化

上記の解法は正しく動作しますが、二分探索には O(log m) の計算コストがかかるため、要素ごとのチェックを繰り返すと全体の計算時間が増加します。

そこで、探索処理を unordered_map（ハッシュマップ）ベースの存在チェックに置き換えることで、O(1) の平均時間で要素の有無を判定できるようになります。これにより、全体的な計算時間を大幅に短縮できます。

実装例（ハッシュマップ版）

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

// ハッシュマップで除外対象を管理し、最大部分配列の和を計算
int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
    unordered_map<int,int> checkVal;
    for(int i=0;i<m;i++)
        checkVal[arr2[i]] = 1;

    int maxSum = −1, sum = 0;
    for (int i = 0; i < n; i++) {
        // 除外対象の要素に到達したら、累積和をリセット
        if (checkVal[arr1[i]]==1) {
            sum = 0;
            continue;
        }
        sum = max(arr1[i], sum + arr1[i]);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main(){
    int arr1[] = { 5, 4, 7, 2, 9 };
    int arr2[] = { 1, 9, 2, 7 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
    cout<<"The maximum Subarray Sum Excluding Certain Elements is "
       <<calcMaxSubArraySum(arr1, arr2, n, m);
    return 0;
}

出力

The maximum Subarray Sum Excluding Certain Elements is 9

まとめ

本記事では、配列 arr1[] から配列 arr2[] に含まれる要素を除外し、残りの要素で最大部分配列の和を求める方法を紹介しました。

• 基本手法： カダネのアルゴリズムを応用し、除外対象の要素が出現した時点で累積和をリセットする。
• 最適化： 二分探索（O(log m)）の代わりに unordered_map を使うことで、要素チェックを O(1) に高速化できる。

データ量が多い場合や、除外チェックを頻繁に行う場合には、ハッシュマップ版の実装が特に有効です。計算量は全体として O(n + m) となり、大規模な配列でも効率的に動作します。