C++で指定された操作で配列の合計を最大化する

説明

（2 * n – 1）個の整数の配列があります。配列内の正確にn個の要素の符号を変更できます。つまり、正確にn個の配列要素を選択し、それぞれに-1を掛けることができます。配列の最大合計を求めます。

例

入力配列が{-2、100、-3}の場合、-2と-3の最大変化符号を取得できます。符号配列を変更すると、-

{2、100、3}であり、この配列の最大合計は105です。

アルゴリズム

• 負の数を数える
• 数値の絶対値を使用して、配列の合計を計算します。
• 数値の絶対値を取得して、配列の最小数を見つけます
• いいえかどうかを確認します。負の数の数は奇数であり、nの値は偶数であり、合計からmを2倍減算します。これは配列の最大合計になります。それ以外の場合、合計の値は配列の最大合計になります。
• 上記の手順を（2 * n – 1）回繰り返します

例

例を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
   int negtiveCnt = 0;
   int sum = 0;
   int m = INT_MAX;
   for (int i = 0; i < 2 * n - 1; ++i) {
      if (arr[i] < 0) {
         ++negtiveCnt;
      }
      sum = sum + abs(arr[i]);
      m = min(m, abs(arr[i]));
   }
   if (negtiveCnt % 2 && n % 2 == 0) {
      sum = sum - 2 * m;
      return sum;
   }
   return sum;
}
int main() {
   int arr[] = {-2, 100, -3};
   int n = 2;
   cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

出力

Maximum sum = 105