C++で3つの整数から式の最大値を求める方法

問題文

0でない3つの整数 a、b、c が与えられます。この3つの整数の間に「加算（+）」と「乗算（*）」の記号を任意の順序で1回ずつ挿入し、式が取り得る最大の値を求めることが課題です。

なお、整数同士の並べ替え（順序の入れ替え）は自由に行って構いませんが、加算記号と乗算記号は必ずそれぞれ1回ずつ使用しなければなりません。

例えば、a = 1、b = 3、c = 5 の場合、最大値は次のようにして 20 になります。

(1 + 3) * 5 = 20

アルゴリズム

最大値は、入力される整数の中に負の数がいくつ含まれているかによって場合分けすることで、効率的に求めることができます。

1. すべての数が正の場合：小さい方の2つの数を足し合わせ、その結果に最も大きい数を掛ける
2. 正の数が2つの場合：正の2つの数を掛け合わせ、残りの数（負の数）を足す
3. 正の数が1つの場合：負の2つの数を掛け合わせ、残りの数（正の数）を足す
4. すべての数が負の場合：最も大きい（絶対値の小さい）2つの整数を足し合わせ、その結果に残りの数を掛ける

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int getMaximumResult(int a, int b, int c){
   int negativeCnt = 0;
   int sum = a + b + c;
   int mul = a * b * c;
   int largest = max(a, max(b, c));
   int smallest = min(a, min(b, c));
   if (a < 0) {
      ++negativeCnt;
   }
   if (b < 0) {
      ++negativeCnt;
   }
   if (c < 0) {
      ++negativeCnt;
   }
   if (negativeCnt == 0) {
      return (sum - largest) * largest;
   }
   else if (negativeCnt == 1) {
      return (mul / smallest) + smallest;
   }
   else if (negativeCnt == 2) {
      return (mul / largest) + largest;
   }
   else if (negativeCnt == 3) {
      return (sum - smallest) * smallest;
   }
}
int main(){
   int a = 1, b = 3, c = 5;
   cout << "Maximum value = " << getMaximumResult(a, b, c) << endl;
   return 0;
}

コードの解説

このプログラムでは、まず負の数の個数（negativeCnt）、3つの数の合計（sum）、積（mul）、最大値（largest）、最小値（smallest）を求めています。その上で、負の数の個数に応じて以下のように処理を切り替えています。

• negativeCnt == 0（すべて正）： 合計から最大値を引くことで「小さい2つの数の和」が得られ、それに最大値を掛けます。
• negativeCnt == 1： 積を最小値で割ることで「正の2つの数の積」が得られ、そこに最小値（負の数）を加えます。
• negativeCnt == 2： 積を最大値で割ることで「負の2つの数の積」が得られ、そこに最大値（正の数）を加えます。
• negativeCnt == 3（すべて負）： 合計から最小値を引くことで「比較的大きい2つの数の和」が得られ、それに最小値を掛けます。

出力結果

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

Maximum value = 20