C++で最大K個の配列要素の符号を反転して最大化する部分配列の合計

問題概要

この問題では、整数の配列と整数 k が与えられます。求めるのは、最大 k 個までの配列要素の符号を反転したときに実現できる部分配列（サブアレイ）合計の最大値を計算するプログラムを C++ で作成することです。

コードの説明 − 配列から作られる部分配列の合計が最大になるように、符号を反転する要素を最大 k 個まで選びます。

入出力例

• 入力 − array = {1, -2, 7, 0}、k = 2
• 出力 − 10
• 説明 − 要素「-2」を 1 つだけ反転すればよいため、配列の合計は 10 となり、これが達成可能な最大値になります。

解法のアプローチ：動的計画法

この問題は動的計画法（DP）とメモ化を組み合わせることで効率的に解けます。i 番目のインデックス以降で得られる最大合計を maxSumij[i][flips] にキャッシュしながら、「その要素の符号を反転する場合」と「反転しない場合」の両方を再帰的に評価し、より良い結果を採用します。

各要素での分岐は次の 2 つです。

• 反転しない場合：a[i] + findSubarraySum(i + 1, flips, n, a, k)
• 反転する場合：-a[i] + findSubarraySum(i + 1, flips + 1, n, a, k)（使用した反転回数 flips を 1 増やす）

部分配列は連続している必要があるため、途中で合計が負になった場合は max(0, ...) によって 0 にリセットし、そこを新しい部分配列の起点として扱います。最後に、すべての開始位置 i について計算した結果の中から最大値を答えとして返します。

計算量

メモ化により、状態数は開始位置と反転回数の組み合わせである O(n × k) となり、各状態の計算は定数時間で行えるため、全体の時間計算量は O(n × k) に抑えられます。

C++ 実装例

ソリューションの動作を示すプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];
int findSubarraySum(int i, int flips, int n, int a[], int k){
    if (flips > k)
        return -1e9;
    if (i == n)
        return 0;
    if (arraySumij[i][flips] != -1)
        return arraySumij[i][flips];
    int maxSum = 0;
    maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
    maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
    arraySumij[i][flips] = maxSum;
    return maxSum;
}
int maxSubarraySumFlip(int a[], int n, int k){
    memset(arraySumij, -1, sizeof(arraySumij));
    int maxSum = -100;
    for (int i = 0; i < n; i++)
        maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
    return maxSum;
}
int main() {
    int a[] = {-3, 56, -1, 8};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 2;
    cout<<"Maximum subarry sum by fipping signs of at most "<<k<<" element is "<<maxSubarraySumFlip(a, n, k);
    return 0;
}

出力

Maximum subarry sum by fipping signs of at most 2 element is 66

この例では、配列 {-3, 56, -1, 8} に対して最大 2 回までの符号反転が許されており、負の要素を反転することで部分配列の合計が最大化されます。