CF题解｜Maximum Product

Codeforces题解｜1385C - Make It Good

---

题目信息 📚

【题目描述】

You are given an array of integers $a_1, a_2, \ldots, a_n$. Find the maximum possible value of $a_i a_j a_k a_l a_t$ among all five indices $(i, j, k, l, t)$ $(i < j < k < l < t)$.

【输入】

The input consists of multiple test cases. The first line contains an integer $t$ $(1 \leq t \leq 2 \times 10^4)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(5 \leq n \leq 10^5)$ — the size of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(-3 \times 10^3 \leq a_i \leq 3 \times 10^3)$ — given array.

It’s guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.

【输出】

For each test case, print one integer — the answer to the problem.

【输入样例】

4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1

【输出样例】

-120
12
0
945

【提示】

In the first test case, choosing $a_1, a_2, a_3, a_4, a_5$ is the best choice: $(-1) \cdot (-2) \cdot (-3) \cdot (-4) \cdot (-5) = -120$.

In the second test case, choosing $a_1, a_2, a_3, a_5, a_6$ is the best choice: $(-1) \cdot (-2) \cdot (-3) \cdot 2 \cdot (-1) = 12$.

In the third test case, choosing $a_1, a_2, a_3, a_4, a_5$ is the best choice: $(-1) \cdot 0 \cdot 0 \cdot 0 \cdot (-1) = 0$.

In the fourth test case, choosing $a_1, a_2, a_3, a_4, a_6$ is the best choice: $(-9) \cdot (-7) \cdot (-5) \cdot (-3) \cdot 1 = 945$.

【题目来源】

https://codeforces.com/problemset/problem/1406/B

---

题目解析 🍉

【题目分析】

排序 + 枚举法。

首先将数组 a 降序排列。

• 如果数组 a 仅包含负数，则最大结果为 a[1] ~ a[5]。如 $-1, -2, -3, -4, -5, -9$ → $res = (-1) \times (-2) \times (-3) \times (-4) \times (-5) = -120$
• 如果数组 a 仅包含正数，则最大结果为 a[1] ~ a[5]。如 $9, 8, 7 , 6 , 5 ,1$ → $res = 9 \times 8 \times 7 \times 6 \times5 = 15120$
• 如果数组 a 既包含正数，又包含负数，则最大结果一定取正数，取以下 3 个的最大值：
  • 5 个最大正数
  • 3 个最大正数 + 2 个最小负数
  • 1 个最大正数 + 4 个最小负数

PS：由于每个数最大能到 $3*10^3$，5个数相乘的数量级最大为 $10^{15}$，会爆 int。

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
LL n, a[N];  // 记得开long long

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 降序排列
    sort(a + 1, a + n + 1, greater<LL>());

    // 枚举可能的最大值
    LL res1 = a[1] * a[2] * a[3] * a[4] * a[5];
    LL res2 = a[1] * a[2] * a[3] * a[n] * a[n - 1];
    LL res3 = a[1] * a[n] * a[n - 1] * a[n - 2] * a[n - 3];
    LL res = max(max(res1, res2), res3);
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}