C++で指定したサイズの重複しない2つの部分配列の最大合計を求める方法

問題概要

この問題では、正の整数で構成される配列と数値 k が与えられます。求めるのは、指定されたサイズ（k）を持つ重複しない2つの部分配列の合計の最大値です。

つまり、サイズ k の互いに重ならない（異なる）2つの部分配列を選び、その合計が最大になる組み合わせを出力するプログラムを作成します。

例で理解しよう

入力：

array = {7, 1, 6, 9, 2} , k = 2

出力：

{7, 1} , {6, 9}

説明：

サイズ2のすべての部分配列とその合計：
{7, 1} : 合計 = 7+1 = 8
{1, 6} : 合計 = 1+6 = 7
{6, 9} : 合計 = 6+9 = 15
{9, 2} : 合計 = 9+2 = 11
→ 合計が最大となる重複しない2つの部分配列は {7,1} と {6,9}

解決アプローチ

この問題に対する単純な解法は、すべての部分配列とその合計を列挙し、互いに重複しない2つの部分配列の組み合わせから最大の合計を見つけることです。しかし、この方法は計算量が大きくなり、非効率です。

より効率的なアプローチは、接頭辞和（プレフィックスサム）配列を利用することです。接頭辞和配列は、配列の先頭から各要素までの累積合計を格納するため、任意の区間の合計を O(1) で計算できます。これを利用しながら、サイズ k の部分配列を順にチェックし、最大の合計を持つ重複しない2つの部分配列のペアを効率的に求めます。

具体的には、配列の右側から走査しながら「右側の最適な部分配列」を記録し、現在位置の左側の部分配列と組み合わせた合計を更新していくことで、全体の最大値を求めます。

実装例

上記の解決策を実装したプログラムは以下のとおりです。

#include <bits/stdc++.h>
using namespace std;
int findSubArraySum(int sum[], int i, int j){
    if (i == 0)
        return sum[j];
    else
        return (sum[j] - sum[i - 1]);
}
void maxSubarray(int arr[],int N, int K){
    int prefixsum[N];
    prefixsum[0] = arr[0];
    for (int i = 1; i < N; i++)
    prefixsum[i] = prefixsum[i - 1] + arr[i];
    pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
    int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1);
    pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
    for (int i = N - 2 * K - 1; i >= 0; i--){
        int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
        if (cur >= secondSubarrayMax.second)
            secondSubarrayMax = make_pair(i + K, cur);
        cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
        if (cur >= maxSubarraySum){
            maxSubarraySum = cur;
            resIndex = make_pair(i, secondSubarrayMax.first);
        }
    }
    cout<<"{ ";
    for (int i = resIndex.first; i <resIndex.first + K; i++)
        cout<<arr[i]<<" ";
    cout<<"}"<<endl<<"{ ";
    for (int i = resIndex.second; i < resIndex.second + K; i++)
        cout<<arr[i]<<" ";
    cout<<"}"<<endl;
}
int main(){
    int arr[] = {2, 5, 1, 2, 7, 3, 0};
    int N = sizeof(arr) / sizeof(int);
    int K = 2;
    cout<<"Two non-overlapping subarrays with maximum sum are \n";
    maxSubarray(arr, N, K);
    return 0;
}

出力

Two non-overlapping subarrays with maximum sum are
{ 2 5 }
{ 7 3 }

まとめ

この記事では、C++を使って指定したサイズ k の重複しない2つの部分配列の最大合計を求める方法を解説しました。接頭辞和配列を活用することで、全組み合わせを総当たりする非効率な手法に比べ、大幅に計算量を抑えた効率的なアルゴリズムを実現できます。配列操作や区間和の計算に慣れたい方にとって、良い練習問題となるでしょう。