【C++】K回の符号反転操作で配列の合計を最大化する方法

問題の概要

サイズ n の整数型配列と、操作回数を表す数値 k が与えられます。私たちの課題は、この配列に対してちょうど k 回の「修正操作」を実行することです。

ここでいう修正操作とは、1 回ごとに配列内の任意の要素 arr[i] を選び、その符号を反転させる(すなわち arr[i] = -arr[i] とする)ことを指します。k 回の操作を終えた時点で、配列全体の合計値が最大になるように操作を行うことが目標です。

例として、入力が arr[] = {7, -3, 5, 4, -1} の場合、最大合計は 20 になります。具体的な手順は以下のとおりです。

• まず -3 を反転します。配列は {7, 3, 5, 4, -1} になります。
• 次に -1 を反転します。配列は {7, 3, 5, 4, 1} となり、合計は 20 です。

アルゴリズムの考え方

この問題を解く基本戦略は非常にシンプルで、「毎回、現時点で最も小さい要素を選んで符号を反転させる」というものです。手順を整理すると次のようになります。

1. 各操作において、現在の配列から最小の要素 arr[i] を探し、それを -arr[i] に置き換えます。
2. 最小要素が 0 になった時点で、それ以上操作しても合計は増えないため、残りの操作は不要となり処理を打ち切って構いません。

負の数を反転すれば正の数になって合計が増加し、逆に正の数を反転すると合計が減少します。そのため、「最小の要素」を狙い撃ちにすることが合計を最大化するための最適な戦略となるのです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n, int k){
    for (int i = 1; i <= k; ++i) {
       int minValue = INT_MAX;
       int index = -1;
       for (int j = 0; j < n; ++j) {
          if (arr[j] < minValue) {
             minValue = arr[j];
             index = j;
          }
       }
       if (minValue == 0) {
          break;
       }
       arr[index] = -arr[index];
    }
    int sum = 0;
    for (int i = 0; i < n; ++i) {
       sum = sum + arr[i];
    }
    return sum;
}
int main(){
    int arr[] = {7, -3, 5, 4, -1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Maximum sum = " << getMaxSum(arr, n, k) << endl;
    return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Maximum sum = 20