C++で最大2つの要素の符号を反転した後の最大部分配列和を求める方法

問題概要

この記事では、配列が与えられたときに「最大2つの要素の符号を反転する」操作を行った後の、最大部分配列和(サブアレイ合計)を求めるC++プログラムを紹介します。

つまり、配列内の任意の要素を最大2つまで選んで符号を反転し、その状態で合計値が最大になる部分配列(連続する要素の並び)を見つけることが目的です。

入力例と出力例

入力:array = {-5, 1, 3, 8, -2, 4, 7}

出力:30

解説:インデックス0から6までのすべての要素を対象に、負の値である -5 と -2 の符号を反転します。元の配列の合計は16ですが、-5→5、-2→2 と反転すると 5+1+3+8+2+4+7 = 30 となり、これが最大の合計になります。

解法アプローチ:動的計画法(DP)

この問題は動的計画法を使うことで効率的に解けます。サイズ1からn(配列の長さ)までのすべての部分配列について、最大和を順に求めていきます。

各時点で考えるのは、次の3つの場合です。

• ケース1 − 部分配列内の2つの要素を反転したときの最大和
• ケース2 − 部分配列内の1つの要素だけを反転したときの最大和
• ケース3 − 要素を1つも反転しないときの最大和

各反復処理では、「現在の要素だけで始まる新たな部分配列」と「直前までの最大和に現在の要素を加えた部分配列」を比較し、大きい方を新しい最大値として採用します。

これらの最大和は maxSum という2次元配列に格納します。maxSum[i][j] は「i番目の要素まで見たとき、ちょうどj個の要素を反転している状態での最大部分配列和」を表します。最終的な答えは、この2次元配列の全要素の中の最大値です。

状態遷移のポイント

• 反転なし(j=0):一般的なカダネのアルゴリズムと同様に、max(arr[i], maxSum[i-1][0] + arr[i]) で更新します。
• 反転1回(j=1):現在の要素を新たに反転する場合は max(0, maxSum[i-1][0]) - arr[i]、すでに1回反転済みの部分配列を延長する場合は maxSum[i-1][1] + arr[i] のうち大きい方を採ります。
• 反転2回(j=2):1回反転済みの状態から現在の要素をさらに反転する場合は maxSum[i-1][1] - arr[i]、すでに2回反転済みの部分配列を延長する場合は maxSum[i-1][2] + arr[i] のうち大きい方を採ります。

この手法により、計算量はO(n)、必要なメモリもO(n)で抑えられるため、大きな配列でも高速に動作します。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
    int maxSubarraySum = 0;
    int* arr = new int[n + 1];
    for (int i = 1; i <= n; i++)
        arr[i] = a[i - 1];
    int** maxSum = new int*[n + 1];
    for (int i = 0; i <= n; i++)
        maxSum[i] = new int[3];
    for (int i = 1; i <= n; ++i) {
        maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
        maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
        if (i >= 2)
            maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
        if (i >= 2)
            maxSum[i][2] = maxSum[i - 1][1] - arr[i];
        if (i >= 3)
            maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
    }
    return maxSubarraySum;
}
int main(){
    int arr[] = {-5, 1, 3, 8, -2, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n);
    return 0;
}

実行結果

Maximum subarray sum after inverting at most two elements is 30