C++で両端の値が同じになる最大合計部分配列を求める方法

はじめに

この記事では、「先頭と末尾の要素の値が等しい」という条件を満たす部分配列（サブ配列）の中から、合計が最大となるものを求めるプログラムについて解説します。

具体的には、整数からなる配列が与えられたとき、両端の要素が同じ値である部分配列を探し、その中で合計が最大になるものを見つけるのが目的です。

アルゴリズムの考え方

この問題は、次の手順で効率的に解くことができます。

1. あらかじめ累積和（プレフィックスサム）を計算しておく。
2. ハッシュマップを使い、各値が最初に出現する位置と最後に出現する位置を記録する。
3. 各要素について「最初の出現位置」から「最後の出現位置」までの区間の合計を累積和で求め、その最大値を答えとする。

同じ値で挟まれた区間の合計は pr[end] - pr[start - 1] のように簡単に計算できるため、全体の処理は高速に行えます。

実装例

#include <bits/stdc++.h>
using namespace std;
// 最大合計を求める関数
int maxValue(int a[], int n) {
    unordered_map<int, int> first, last;
    int pr[n];
    pr[0] = a[0];
    // 累積和の計算と、各値の出現位置の記録
    for (int i = 1; i < n; i++) {
        pr[i] = pr[i - 1] + a[i];
        if (first[a[i]] == 0)
            first[a[i]] = i;
        last[a[i]] = i;
    }
    int ans = 0;
    // 各値について、最初と最後の出現位置に挟まれた区間の合計を評価
    for (int i = 0; i < n; i++) {
        int start = first[a[i]];`
        int end = last[a[i]];`
        ans = max(ans, pr[end] - pr[start - 1]);
    }
    return ans;
}
int main() {
    int arr[] = { 1, 3, 5, 2, 4, 18, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxValue(arr, n);
    return 0;
}

出力

37

コードの解説

入力配列 { 1, 3, 5, 2, 4, 18, 2, 3 } の場合を考えてみましょう。値 3 はインデックス 1 と 7 に出現しているため、対応する部分配列は { 3, 5, 2, 4, 18, 2, 3 } となり、その合計は 37 です。

同様に、値 2 で挟まれた区間 { 2, 4, 18, 2 } の合計は 26、一度しか出現しない値の区間の合計はそれ以下になります。したがって、条件を満たす部分配列の中で最大の合計は 37 となり、これが出力されます。

このように、累積和とハッシュマップを組み合わせることで、各値の区間合計を繰り返し計算することなく効率的に最大値を求めることができます。