C++でn個の要素の符号を反転して配列の合計を最大化する方法

問題の概要

(2 × n − 1) 個の整数からなる配列が与えられます。この配列からちょうど n 個の要素を選び、それぞれの符号を反転(−1倍)することができます。この操作を行った結果として得られる配列の合計の最大値を求めるのが課題です。

例

入力配列が {-2, 100, -3} の場合を考えてみましょう。-2 と -3 の符号を反転すると、配列は {2, 100, 3} となり、合計は 105 になります。これがこの配列で達成できる最大の合計です。

アルゴリズム

この問題は、以下の手順で効率的に解くことができます。

1. 配列内の負の数の個数を数えます。
2. すべての要素の絶対値の合計を求めます。
3. 絶対値が最小となる要素の値 m を求めます。
4. 負の数の個数が奇数であり、かつ反転する要素数 n が偶数である場合は、合計から「2 × m」を引いた値が最大合計となります。それ以外の場合は、絶対値の合計がそのまま最大合計になります。

これらの処理は、配列の全要素(2 × n − 1 個)に対して一度の走査で完了します。

なぜこの方法で正しいのか

同じ要素に符号反転を2回適用すると元に戻るため、重要になるのは反転回数の偶奇です。

• 負の数が偶数個なら、それらを2個ずつペアにして反転することで、すべての要素を正にできます。
• n が奇数の場合は、1回分を負の要素の反転に使い、残りの反転を2回ずつのペアに振り分ければ、やはりすべての要素を正にできます。

一方、負の数が奇数個で n が偶数の場合は、どのように反転を割り当てても少なくとも1つの要素が負のまま残ってしまいます。このとき損失を最小限に抑えるには、絶対値が最も小さい要素を負のままにするのが最善です。したがって、合計から「2 × 最小絶対値」を引いた値が答えになります。

C++での実装例

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

int getMaxSum(int *arr, int n) {
    int negativeCnt = 0;
    int sum = 0;
    int m = INT_MAX;

    // 配列の全要素 (2n - 1 個) を一度だけ走査する
    for (int i = 0; i < 2 * n - 1; ++i) {
        if (arr[i] < 0) {
            ++negativeCnt;
        }
        sum += abs(arr[i]);
        m = min(m, abs(arr[i]));
    }

    // 負の数が奇数個で、かつ n が偶数の場合のみ調整が必要
    if (negativeCnt % 2 && n % 2 == 0) {
        return sum - 2 * m;
    }
    return sum;
}

int main() {
    int arr[] = {-2, 100, -3};
    int n = 2;
    cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
    return 0;
}

実行結果

Maximum sum = 105

計算量

• 時間計算量: 配列を一度走査するだけなので O(n)
• 空間計算量: 追加の記憶領域が不要なため O(1)