C++でちょうどK回の符号反転後に得られる最大配列合計

正と負の整数で構成される配列と数値Kが与えられます。求めるのは、配列の要素に対してちょうどK回の変更を行った後の合計の最大値です。ここでいう1回の変更操作とは、単一の要素に-1を掛けて符号を反転することを指します。

アルゴリズムの考え方

基本的なアプローチは、すべての負の数を正の数に変換することです。負の数がN個ある場合、まず配列をソートしてから以下の方針で処理します。

• N < K の場合：N回の操作ですべての要素が正となり、残りはK−N回の操作になります。
• K−N が偶数の場合：残りのK−N回の符号反転は互いに打ち消し合うため、何もする必要がありません。
• K−N が奇数の場合：配列内の最小値（最も絶対値の小さい要素）の符号を1回だけ反転します。-1を掛ける回数が奇数回の場合は1回掛けることと同じ結果になるため、これで全体の合計が最大になります。

また、N > K の場合は、K個の負の数の符号を反転して配列の合計を求めるだけで、それが最大値となります。

入力例

Arr[] = { 0, -2, 6, 4, 8, 2, -3 }, K = 4

出力例

Maximum array sum is : 25

説明：4回の変更は次のようになります。

1. 0,2,6,4,8,2,-3 → -2 を 2 に変更
2. 0,2,6,4,8,2,3 → -3 を 3 に変更
3. 0,2,6,4,8,2,3 → 2 を -2 に変更
4. 0,2,6,4,8,2,3 → -2 を 2 に変更

最大合計は 25

別の入力例

Arr[] = { -1, -2, -3, -4, -5, -6, -7 }, K = 4

出力例

Maximum array sum is : 16

説明：絶対値の大きい負の数から順に4つ反転します。

1. -7 を 7 に変更
2. -6 を 6 に変更
3. -5 を 5 に変更
4. -4 を 4 に変更
最大合計は 16（-1 + (-2) + (-3) + 4 + 5 + 6 + 7）

プログラムの実装方針

• 整数型配列 Arr[] に整数を格納します。
• 整数 size に配列の長さを、K に操作回数を設定します。
• 関数 returnSum(int arr[], int n, int k) は、配列・そのサイズ・k を受け取り、ちょうどk回の操作後の合計の最大値を返します。
• まず sort(arr, arr + n) で配列を昇順にソートします。
• 負の要素に対して arr[i] * -1 の操作を、配列の末尾に達するか k が0になるまで適用します。
• k が負の要素の数より小さい場合は、この手順だけでk個の負の要素が反転されます。
• k が余る場合は、残りのkが奇数か偶数かを判定します。
• 残りのkが奇数なら、最小要素の符号を1回だけ反転します。
• 残りのkが偶数なら、反転しても結果が変わらないため何もしません。
• 最後に配列全体の合計を計算して返します。

C++による実装例

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

int returnSum(int arr[], int n, int k){
    // 配列をソート
    sort(arr, arr + n);

    // 小さい値から順に負の要素の符号を反転
    // k回ごとに1つの負の要素が正になります
    for (int i = 0; i < n; i++)
        if (k > 0 && arr[i] < 0){
            arr[i] = arr[i] * -1;
            k--;
        }

    // kが残っていて奇数の場合、
    // 最小要素の符号を1回だけ反転
    if (k % 2 == 1) {
        int minVal = arr[0];
        int pos = 0; // 最小要素のインデックス
        for (int i = 1; i < n; i++)
            if (arr[i] < minVal){
                minVal = arr[i];
                pos = i;
            }
        arr[pos] *= -1;
    }

    // 配列全体の合計を計算
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    return sum;
}

int main(){
    int Arr[] = { -3, 4, -3, 6, 8 };
    int size = 5;
    int K = 4;
    cout << "ちょうどk回の変更後に得られる最大配列合計 : "
         << returnSum(Arr, size, K) << endl;
    return 0;
}

出力

ちょうどk回の変更後に得られる最大配列合計 : 24

計算量について

このアルゴリズムの時間計算量は、ソートに支配されるため O(n log n) です。その後の走査は線形時間 O(n) で完了し、追加のメモリは不要なため空間計算量は O(1) となります。負の数を優先的に反転し、余った操作を最小要素に割り当てるという貪欲法により、ちょうどK回の制約を満たしながら常に最大の合計を効率的に求められます。