C++で最大1つの要素を削除した場合の最大合計サブ配列を求める方法

問題の概要

この問題では、整数の配列が与えられます。私たちのタスクは、最大で1つの要素を削除したときに得られる最大合計サブ配列を求めるプログラムをC++で作成することです。

つまり、配列から1つの要素を取り除いたときに、残りの要素の合計が最大になるような要素を見つける必要があります。

具体例で問題を理解する

入力: array = {5, 1, 9, 2, -1, 7}

出力: 24

解説: 配列から -1 を削除すると、考えられるすべての組み合わせの中で最大の合計 24 が得られます。

解法のアプローチ

この問題に対する単純な解決策の1つは、配列の最小要素を見つけて、残りのすべての要素の合計を計算する方法です。しかし、この方法では「削除しない方が合計が大きくなるケース」などに正しく対応できません。

そこで有効なのがカダネのアルゴリズム(Kadane's Algorithm)の応用です。この手法では、以下の手順で最大合計を計算します。

1. 配列の先頭から各要素 i までの最大部分配列和(startSum)を計算する
2. 配列の末尾から各要素 i までの最大部分配列和(endSum)を計算する
3. 要素 i を削除した場合の合計を startSum[i-1] + endSum[i+1] として求め、全体の最大値を更新する

この方法により、どの要素をスキップしたときに最大の合計が得られるかを効率的に判定できます。

C++での実装例

上記の解法を実装したプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
int maxSubarraySum(int array[], int n){
    int startSum[n], endSum[n];
    int maxSum = array[0], overAllMax = array[0];
    startSum[0] = array[0];
    for (int i = 1; i < n; i++){
        maxSum = max(array[i], maxSum + array[i]);
        overAllMax = max(overAllMax, maxSum);
        startSum[i] = maxSum;
    }
    maxSum = endSum[n-1] = array[n-1];
    for (int i = n-2; i >= 0; i--){
        maxSum = max(array[i], maxSum + array[i]);
        overAllMax = max(overAllMax, maxSum);
        endSum[i] = maxSum;
    }
    int SubArraySum = overAllMax;
    for (int i = 1; i < n - 1; i++)
        SubArraySum = max(SubArraySum, startSum[i - 1] + endSum[i + 1]);
    return SubArraySum;
}
int main()
{
    int array[] = {5, 7, 1, -1, 4, 2, 9};
    int n = sizeof(array) / sizeof(array[0]);
    cout<<"The maximum subarray after removing one element is "<<maxSubarraySum(array, n);
    return 0;
}

出力結果

The maximum subarray after removing one element is 28

アルゴリズムの計算量

この解法の時間計算量は O(n) であり、配列を数回走査するだけで済みます。空間計算量も O(n) で、startSum と endSum の2つの補助配列が必要です。

単純に最小要素を削除するアプローチと比較して、この方法は「要素を削除しない場合」も含めた最適解を正しく求められる点で優れており、負の値を含むあらゆる配列に対して堅牢に動作します。