C++で指定した操作を実行した後の配列における最大積の求め方

このチュートリアルでは、C++を用いて「指定された操作を実行した後に配列で得られる最大の積」を求めるプログラムについて詳しく解説します。

問題の概要

サイズNの整数型配列が与えられます。私たちのタスクは、次のいずれかの操作を合計N-1回実行し、最終的に残る値の積が最大になるようにすることです。

• 操作1: a[j] の値を a[i]*a[j] に書き換え、a[i] を配列から取り除く(要素同士を掛け合わせて統合する)
• 操作2: a[i] の値をそのまま削除する(この操作は全体で1回のみ使用可能)

つまり、すべての操作が終わった時点で配列には要素が1つだけ残り、その値が可能な限り大きくなるような手順を見つける必要があります。

アルゴリズムの考え方

最大の積を得るためには、配列内の各要素の符号に着目することが重要です。

• 負の数: 負の数が奇数個含まれる場合、積は負になってしまいます。そこで、絶対値が最小の負の数を1つだけ除外対象とし、残りの負の数を偶数個にします。
• ゼロ: ゼロが1つでも混ざると積は必ず0になるため、削除の優先候補となります。
• 正の数と残りの負の数: これらはすべて掛け合わせることで積を最大化できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 操作内容を出力する関数
void MaximumProduct(int a[], int n) {
   int cntneg = 0;
   int cntzero = 0;
   int used[n] = { 0 };
   int pos = -1;
   for (int i = 0; i < n; ++i) {
      if (a[i] == 0) {
         used[i] = 1;
         cntzero++;
   }
   if (a[i] < 0) {
      cntneg++;
      if (pos == -1 || abs(a[pos]) > abs(a[i]))
         pos = i;
      }
   }
   if (cntneg % 2 == 1)
      used[pos] = 1;
   if (cntzero == n || (cntzero == n - 1 && cntneg == 1)) {
      for (int i = 0; i < n - 1; ++i)
         cout << 1 << " " << i + 1 << " " << i + 2 << endl;
      return;
   }
   int lst = -1;
   for (int i = 0; i < n; ++i) {
      if (used[i]) {
         if (lst != -1)
            cout << 1 << " " << lst + 1 << " " << i + 1 << endl;
         lst = i;
      }
   }
   if (lst != -1)
      cout << 2 << " " << lst + 1 << endl;
   lst = -1;
   for (int i = 0; i < n; ++i) {
      if (!used[i]) {
         if (lst != -1)
            cout << 1 << " " << lst + 1 << " " << i + 1 << endl;
         lst = i;
      }
   }
}
int main() {
   int a[] = { 5, -2, 0, 1, -3 };
   int n = sizeof(a) / sizeof(a[0]);
   MaximumProduct(a, n);
   return 0;
}

実行結果

2 3
1 1 2
1 2 4
1 4 5

出力の読み方とコードの解説

出力の各行は、実行すべき操作を表しています。

• 「2 i」: 配列のi番目の要素を単独で削除する操作です。
• 「1 i j」: i番目の要素をj番目の要素に乗算して統合する(a[j] ← a[i]*a[j])操作で、その後a[i]は配列から取り除かれます。

サンプル配列 { 5, -2, 0, 1, -3 } の場合、まずゼロ(3番目の要素)が削除対象としてマークされます。負の数は2個(-2と-3)で偶数なので、追加の除外は不要です。そのため最初の出力「2 3」でゼロを削除し、続く「1」の操作で残りの要素 5、-2、1、-3 を順番に掛け合わせていきます。最終的に残る積は 5 × (-2) × 1 × (-3) = 30 となり、これがこの配列で達成できる最大の積です。

このように、負の数・ゼロ・正の数それぞれの性質を考慮して処理の順序を決めることで、効率的に最大積を求めることができます。