C++算法题解：最大乘积问题的贪心策略与实现

问题分析与核心逻辑

题目要求从给定的 n 个整数中选取 5 个数，使它们的乘积最大。输入可能包含多组测试数据，且数字范围可能涉及负数。若仅考虑正数，直接选取最大的五个数即可；但负数的存在使得“负负得正”成为可能，因此必须分类讨论。

将数组从小到大排序后，我们可以重点关注两端的数据：
- 尾部（a[n] ~ a[n-4]）：最大的正数或绝对值较小的负数。
- 头部（a[1] ~ a[4]）：最小的负数（绝对值最大）或小的正数。

第1步：确定候选组合

为了覆盖所有可能产生最大乘积的情况，我们需要比较以下三种组合：

1. 全正数情形（或无明显负数优势）：选取最大的 5 个数。
     乘积表达式：a[n] * a[n-1] * a[n-2] * a[n-3] * a[n-4]
2. 双负数情形：选取 2 个最小的负数（绝对值最大，乘积为正且极大）和 3 个最大的正数。
     乘积表达式：a[n] * a[n-1] * a[n-2] * a[1] * a[2]
3. 四负数情形：选取 4 个最小的负数和 1 个最大的数（通常为最大正数，若全为负数则选最大的那个负数）。
     乘积表达式：a[n] * a[1] * a[2] * a[3] * a[4]

注意：当所有数均为负数时，最大的 5 个数即为绝对值最小的 5 个负数，其乘积也符合情况 1 的逻辑，因此无需单独编写全负数的特判分支。

第2步：代码实现结构

使用 long long 类型防止乘法溢出。对于每组数据，读入数组后进行排序，随后计算上述三种情况的乘积，并取最大值输出。

第3步：完整 C++ 代码

以下是基于标准模板库的完整实现，包含文件重定向以匹配常见的 OJ 评测格式：

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

// 定义足够大的数组以容纳输入
long long a[100005];
int n, t;

int main()
{
    // 打开输入输出文件
    freopen("maximum.in", "r", stdin);
    freopen("maximum.out", "w", stdout);
    
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; ++i)
            cin >> a[i];
        
        // 对数组进行升序排序
        sort(a + 1, a + n + 1);
        
        // 计算三种关键组合的最大值
        // 1. 最大5个数: a[n]~a[n-4]
        // 2. 最大3正+最小2负: a[n]*a[n-1]*a[n-2]*a[1]*a[2]
        // 3. 最大1正(或最大负)+最小4负: a[n]*a[1]*a[2]*a[3]*a[4]
        long long res1 = a[n] * a[n-1] * a[n-2] * a[n-3] * a[n-4];
        long long res2 = a[n] * a[n-1] * a[n-2] * a[1] * a[2];
        long long res3 = a[n] * a[1] * a[2] * a[3] * a[4];
        
        cout << max(res1, max(res2, res3)) << endl;
    }
    return 0;
}

样例验证

我们可以通过提供的样例来验证逻辑的正确性：

• 样例 1: -1 -2 -3 -4 -5。
  排序后为 -5 -4 -3 -2 -1。全选负数，最大乘积为 -1*-2*-3*-4*-5 = -120。代码中 res1 即为此值，正确。
• 样例 2: -1 -2 -3 1 2 -1。
  排序后为 -3 -2 -1 -1 1 2。
  res1 (5大): 2*1*-1*-1*-2 = -4
  res2 (3大2小): 2*1*-1 * -3*-2 = 12
  res3 (1大4小): 2 * -3*-2*-1*-1 = 12
  结果为 12，正确。
• 样例 3: -1 0 0 0 -1 -1。
  排序后 -1 -1 -1 0 0 0。无论怎么选，只要有0参与且无法凑出更多负数抵消，结果往往为0或负数。最大非零尝试受限于负数数量，最终最大值取 0，正确。
• 样例 4: -9 -7 -5 -3 -2 1。
  排序后 -9 -7 -5 -3 -2 1。
  res2 (3大2小): 1 * (-2)*(-3) * (-9)*(-7) = 1 * 6 * 63 = 378? 等等，这里需要仔细检查逻辑。实际上，res2是取最大的三个正数(只有1)和最小的两个负数(-9,-7)，乘积为 1 * 1 * 1 * (-9) * (-7) 这里逻辑有误，原题选5个数。最大的三个数是 1, -2, -3。最小的两个是 -9, -7。组合为 1*(-2)*(-3)*(-9)*(-7) = 378？不对，题目样例输出是 945。
  修正分析：样例4输出945。 945 = 9 * 7 * 5 * 3 * 1 ?? No.
  让我们重新看样例4数据：-9, -7, -5, -3, -2, 1。
  如果选四个负数和一个最大正数：(-9)*(-7)*(-5)*(-3)*1 = 945。这是 res3 的情况吗？
  res3 公式：a[n] * a[1] * a[2] * a[3] * a[4]。
  a[1]=-9, a[2]=-7, a[3]=-5, a[4]=-3, a[n]=1。
  乘积：1 * (-9) * (-7) * (-5) * (-3) = 945。是的，res3 捕获了这种情况。

总结

解决此类“最大乘积”问题，关键在于打破“只选最大”的思维定势，充分考量负数两两成对的特性。通过排序预处理，仅需常数次的比较即可得出最优解。以上就是 C++ 解决最大乘积问题的详细内容，更多关于 C++ 算法技巧的资料请关注本站其它相关文章！