C++プログラム：先頭と末尾の値が同じになる最大合計部分配列を求める方法

この問題では、正の整数のみから構成されるサイズnの配列arr[]が与えられます。求めるのは、部分配列（サブ配列）の先頭要素と末尾要素が同じ値であるようなものの中で、要素の合計が最大となる部分配列です。

問題の概要

ここでの課題は、部分配列の開始インデックスiと終了インデックスjにおける要素が等しい、すなわち arr[i] == arr[j] を満たす部分配列を見つけ出し、その要素の合計を最大化することです。

入力例

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

出力例

23

説明

先頭と末尾が同じ要素になっている部分配列は以下の通りです。
{2, 1, 3, 5, 6, 2} = 2 + 1 + 3 + 5 + 6 + 2 = 19
{3, 5, 6, 2, 4, 3} = 3 + 5 + 6 + 2 + 4 + 3 = 23

したがって、最大合計は 23 となります。

解法のアプローチ

この問題を効率的に解く鍵は、配列がすべて正の値で構成されているという点にあります。正の値のみの場合、部分配列の長さが長くなるほど合計も大きくなるため、各値について「最も左側に出現する位置」と「最も右側に出現する位置」を特定すれば、その値を両端とする最大サイズの部分配列が得られます。

具体的な手順は以下の通りです。

1. 累積和の配列sumArrを作成し、各インデックスまでの要素の合計を事前計算しておきます。
2. ハッシュマップを使って、各値の最初の出現位置（startIndex）と最後の出現位置（endIndex）を記録します。
3. 各要素について、その値を先頭・末尾とする最大範囲の部分配列の合計を sumArr[right] - sumArr[left - 1] で計算し、maxSumを更新していきます。

この方法により、時間計算量O(n)で問題を解くことができます。

C++による実装例

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

int maxValue(int arr[], int n) {
    unordered_map<int, int> startIndex, endIndex;
    int sumArr[n];
    sumArr[0] = arr[0];
    for (int i = 1; i < n; i++) {
        sumArr[i] = sumArr[i - 1] + arr[i];
        if (startIndex[arr[i]] == 0)
            startIndex[arr[i]] = i;
        endIndex[arr[i]] = i;
    }
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int left = startIndex[arr[i]];
        int right = endIndex[arr[i]];
        maxSum = max(maxSum, sumArr[right] - sumArr[left - 1]);
    }
    return maxSum;
}

int main() {
    int arr[] = { 2, 1, 3, 5, 6, 2, 4, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "先頭と末尾の値が同じ最大合計部分配列の合計値は "
         << maxValue(arr, n);
    return 0;
}

実行結果

先頭と末尾の値が同じ最大合計部分配列の合計値は 23

まとめ

本記事では、先頭と末尾の値が一致する部分配列の中から合計が最大のものを求めるC++プログラムを紹介しました。累積和とハッシュマップを組み合わせることで、各値の出現範囲を一度の走査で把握でき、O(n)の計算量で効率的に解ける点がポイントです。すべての要素が正であるという前提条件があるため、「範囲が広いほど合計が大きくなる」という性質を利用できることも、この解法の重要なポイントです。