1. 问题引入从一道经典国赛题说起最近在整理历年算法竞赛的真题翻到了第九届蓝桥杯国赛的这道“最大乘积”。题目本身描述很简洁但背后涉及到的组合优化、贪心策略和边界处理却非常值得拿出来好好聊聊。很多朋友第一次看到这类题目可能会觉得“不就是选几个数让乘积最大吗”但实际动手写起来就会发现各种细节上的坑比如负数的处理、零的存在、以及如何证明贪心策略的正确性。这道题可以说是考察选手对问题本质理解深度和代码实现严谨性的一个绝佳样本。今天我们就来彻底拆解这道题。我会从最朴素的暴力思路开始一步步分析为什么暴力不可行然后引出核心的贪心策略并详细解释这个策略为什么是有效的。接着我们会手把手写出代码实现并重点讨论那些容易出错的边界情况。最后我还会分享一些我在刷题和教学中总结出来的、关于这类“最值”问题的通用思考框架。无论你是正在备赛的选手还是对算法感兴趣的开发者相信这篇内容都能给你带来一些实实在在的收获。2. 题目重述与核心诉求分析首先我们需要把题目从竞赛语境“翻译”成我们更容易理解的工程问题。原题大意通常是给定一个包含 N 个整数的集合可能包含正数、负数和零我们需要从中选出 M 个数M ≤ N使得这 M 个数的乘积最大。我们需要输出这个最大的乘积。这里有几个关键点需要立刻明确它们直接决定了我们解题的整个方向2.1 输入数据的特征题目没有明确说但根据蓝桥杯一贯的风格和此类问题的普遍设定我们可以推断整数范围数字通常是整数可能很大比如绝对值在 10^9 量级这意味着乘积可能会非常巨大远超任何标准整数类型如int,long long的表示范围。因此处理大数运算是我们必须提前考虑的问题。数据规模N 可能会比较大比如 10^5 量级而 M 也可能接近 N。这直接宣判了暴力枚举所有组合的死刑因为组合数 C(N, M) 是天文数字。元素类型明确包含正数、负数和零。这是本题的难点和精华所在。正数乘正数变大负数乘负数也能变正数而零则是一个“重置器”。如何权衡这三者是策略的核心。2.2 输出要求的隐含条件输出最大乘积。在算法竞赛中如果结果可能很大通常有两种处理方式要求输出结果对某个大质数如 10^97取模后的值。或者像本题更可能的情况因为数字本身可能很大最大乘积可能是一个天文数字题目会允许或要求你输出这个数的字符串形式或者直接输出这个数在 Python 等支持大整数的语言中。 我们需要根据题目描述确认这一点。为了通用性我们的讨论将基于“结果可能非常大”这一前提并给出相应的处理建议。2.3 问题本质的转化“从 N 个数中选 M 个使乘积最大”。这听起来像是一个搜索或动态规划问题。但结合数据规模我们必须寻找更聪明的办法。一个关键的洞察是乘积的大小主要由绝对值大的数决定而符号正负则由负数的个数决定。这提示我们可以将问题分解为两个子问题如何选择一组绝对值尽可能大的数在保证绝对值大的前提下如何确保最终的乘积符号为正因为正数 零 负数基于这个洞察一个贪心策略的轮廓就浮现出来了。3. 贪心策略的推导与详细论证为什么贪心算法在这里是有效的我们需要一步步推理而不是直接记住结论。3.1 排序是第一步既然我们关心绝对值最直接的做法是将所有数按绝对值从大到小排序。这样排在前面的数对乘积大小的“贡献潜力”最大。这是贪心选择的基础我们倾向于优先选取绝对值大的数。3.2 核心挑战负数的处理如果所有数都是非负数正数和零那么问题非常简单直接选取排序后前 M 个最大的正数即可如果不足 M 个则结果为零或由零和正数构成。 麻烦在于负数。两个负数相乘得到正数。因此成对出现的负数可以成为我们增大乘积的“帮手”。这就引出了最核心的贪心策略将正数和负数分开存储并分别按绝对值从大到小排序。我们总是希望优先选取绝对值大的正数。对于负数我们必须成对选取。因为单个负数会使乘积变负而我们总是在追求最大乘积正数。因此我们每次考虑负数时都是考虑“一对”负数即绝对值最大的两个负数。3.3 策略的步骤化描述假设我们有数组pos存储正数已按绝对值降序数组neg存储负数已按绝对值降序注意负数绝对值越大其本身值越小。 我们需要选择 M 个数。初始化结果res 1乘法的单位元。我们用两个指针i和j分别指向pos和neg的头部。在还需要选数的情况下我们面临以下几种选择选择两个正数即pos[i]和pos[i1]。贡献为pos[i] * pos[i1]。选择两个负数即neg[j]和neg[j1]。贡献为neg[j] * neg[j1]这是一个正数。如果 M 是奇数我们还需要一个“种子”第一个数不能选一对负数因为那样会剩下一个数无法配对。因此对于奇数的 M第一个数我们必须选择一个最大的正数如果存在即pos[i]。之后 M 变为偶数我们就可以一直进行“二选一”的决策了。所以算法的骨架是如果 M 是奇数且存在正数先选一个最大的正数 (pos[i])i,M--。如果第一步无法执行即 M 是奇数但没有正数那么最大乘积很可能就是零如果存在零或者是绝对值最小的 M 个数的乘积此时结果必为负数或零。这是一个关键的边界情况我们后面细说。现在 M 是偶数。我们进入一个循环只要还需要选数M 0并且还有成对的数可选我们就比较pos[i]*pos[i1]和neg[j]*neg[j1]的大小。选择乘积更大的那一对将其乘入res并移动相应的指针i2或j2同时M - 2。3.4 为什么贪心是有效的—— 交换论证法我们可以用“交换论证”来非正式地证明这个贪心策略。假设我们有一个最优解它没有按照我们的贪心策略选择。那么在这个最优解中我们总能找到一对选择将其替换成我们的贪心选择而不会使结果变差。 例如假设在某个步骤最优解选择了一对乘积较小的数比如a1*a2而贪心选择建议的是一对乘积更大的数b1*b2。因为所有数都是按绝对值排序的b1和b2的绝对值之和在正数情况下或乘积在负数成对情况下不会小于a1和a2的。用b1, b2替换a1, a2乘积不会减小。通过一系列这样的替换我们可以将任何最优解逐步转变为我们的贪心解从而证明贪心解至少和最优解一样好。4. 代码实现与逐行解析理论说清楚了我们来看代码。这里我用 Python 来实现因为它内置了大整数方便我们专注于算法逻辑。其他语言需要注意大数处理。def max_product(nums, M): 计算从数组nums中选取M个数所能得到的最大乘积。 Args: nums: List[int], 输入的整数数组 M: int, 需要选择的数的个数 Returns: int: 最大乘积Python int 可表示任意大整数 # 1. 分离正数和负数 positives [x for x in nums if x 0] negatives [x for x in nums if x 0] zero_exists 0 in nums # 2. 排序正数按值降序本身就是绝对值降序负数按值升序即绝对值降序 positives.sort(reverseTrue) negatives.sort() # 对负数sort()默认升序例如 [-5, -4, -1] n_pos, n_neg len(positives), len(negatives) res 1 i, j 0, 0 # i指向正数j指向负数 # 3. 处理 M 为奇数的情况需要先找一个“种子” if M % 2 1: if i n_pos: # 有正数选最大的正数作为种子 res * positives[i] i 1 M - 1 else: # 没有正数这是最棘手的边界情况 # 情况A如果存在零那么最大乘积至少是0。但我们可以选M个零吗不能因为MN我们可能没有M个零。 # 实际上当没有正数且M为奇数时任何选法得到的乘积都是非正的零或负。 # 为了得到“最大”的乘积我们应该选绝对值最小的M个数这样负数的乘积负得最少或者选零。 if zero_exists: # 如果存在零最大乘积就是0前提是我们可以选到零 # 但题目要求选M个如果零的个数不够M个我们还是要搭配一些负数结果仍是0因为任何数乘0得0 # 简便做法直接返回0 return 0 else: # 没有零全是负数。那么最大乘积负得最小就是绝对值最大的M个负数的乘积因为负数绝对值越大本身值越小乘积负得越厉害这里需要仔细 # 举例nums [-5, -4, -3, -2, -1], M3。 # 我们想要乘积最大即负得最少。乘积(-5)*(-4)*(-3) -60, (-4)*(-3)*(-2) -24, (-3)*(-2)*(-1) -6。 # 可见选绝对值最小的三个负数-1,-2,-3乘积是-6是最大的。 # 所以应该将负数按绝对值升序即本身值降序排序选前M个。 negatives.sort(reverseTrue) # 变成 [-1, -2, -3, -4, -5] for k in range(M): res * negatives[k] return res # 4. 现在 M 是偶数我们进行成对选择 while M 0: pair_pos, pair_neg 0, 0 # 计算正数对和负数对的乘积如果可用 if i 1 n_pos: pair_pos positives[i] * positives[i 1] if j 1 n_neg: pair_neg negatives[j] * negatives[j 1] # 决策选择乘积更大的一对 if pair_pos 0 and pair_neg 0: # 没有成对的数可选了说明剩下的数不足两个但M还是偶数0。 # 这通常发生在数不够选的情况下。此时如果存在零结果可以是0否则只能硬选。 # 实际上如果走到这里意味着 n_pos-i n_neg-j M可用的单个数不够M个了。 # 但根据题目MN这不应该发生除非我们之前的选取策略有问题。这是一个安全保护。 # 更合理的处理是如果数不够我们应该回溯或采用其他策略。但根据贪心此时我们应该用单个正数或零来填充。 # 简化处理如果还有正数选正数否则如果有零结果为零否则选负数此时乘积必为负或零。 # 但为了逻辑清晰我们假设输入总是有解的。在实际竞赛中需要仔细处理。 break if pair_pos pair_neg: # 注意当相等时任选一个均可这里优先正数对 res * pair_pos i 2 else: res * pair_neg j 2 M - 2 return res # 测试用例 if __name__ __main__: # 示例1混合情况 nums1 [1, 2, 3, 4, -5, -6] M1 4 print(fnums: {nums1}, M{M1}, max product: {max_product(nums1, M1)}) # 应输出 360 (3*4*-5*-6) # 示例2M为奇数无正数有零 nums2 [-2, -1, 0] M2 3 print(fnums: {nums2}, M{M2}, max product: {max_product(nums2, M2)}) # 应输出 0 # 示例3全负数M为奇数无零 nums3 [-5, -4, -3, -2, -1] M3 3 print(fnums: {nums3}, M{M3}, max product: {max_product(nums3, M3)}) # 应输出 -6 (-1*-2*-3)代码关键点解析分离与排序positives.sort(reverseTrue)确保正数从大到小。negatives.sort()对负数默认升序例如[-5, -4, -1]这恰好是按绝对值从大到小排列因为 -5 -4 -1但 |-5| |-4| |-1|。这个细节很重要。奇数 M 的种子处理这是代码中最复杂的部分。如果奇数 M 且有正数很简单。如果没有正数就需要分情况讨论有零则结果为 0无零则全是负数此时最大乘积负得最少是绝对值最小的 M 个负数的乘积因此需要将负数按值降序即绝对值升序排序后选取。很多粗心的实现会在这里出错。成对选择循环while M 0循环中我们计算当前可用的正数对和负数对的乘积。比较时我使用了pair_pos pair_neg这是一个细节。当两者相等时选择正数对还是负数对最终结果可能相同但选择正数对可以避免过早耗尽负数对在某些特殊序列下可能更优。这属于微优化不影响正确性。循环终止条件代码中有一个if pair_pos 0 and pair_neg 0的判断这是一个保护性逻辑。在理想情况下按我们的贪心策略不会出现还有 M偶数要选但没有成对数可用的情况。但如果数据非常极端比如大量零和单个正数这个保护可以防止无限循环或错误。在实际竞赛中需要根据题目数据范围判断是否真的需要这么写。5. 边界情况、踩坑点与测试策略即使理解了算法实现时也极易掉进坑里。下面是我总结的几个关键陷阱和测试方法5.1 全是负数且 M 为奇数这是最容易错的情况。例如nums [-10, -9, -8, -7], M 3。没有正数没有零。错误思路直接套用成对选择。但 M 是奇数第一步找不到正数种子可能直接返回 0 或出错。正确做法如我们代码所示此时应取绝对值最小的 3 个数即 -7, -8, -9乘积为(-7)*(-8)*(-9) -504。而如果取绝对值最大的三个-10, -9, -8乘积是-720更小。所以目标是“负得最少”选绝对值最小的。5.2 零的存在性处理零是一个特殊元素。如果最大乘积可以是正数我们绝对不选零因为零会“毁灭”乘积。只有当无法得到正数乘积时零才是最优解因为 0 任何负数。在我们的贪心策略中零通常被排除在positives和negatives之外。我们用一个布尔值zero_exists记录。在无法得到正数结果时例如奇数 M 且无正数如果存在零我们就直接返回 0。5.3 M 等于 1 的情况M1 时问题退化为“找最大值”。我们的算法需要兼容奇数 M 处理分支会先执行。如果存在正数选最大正数如果没有正数则选最大的数可能是零或绝对值最小的负数。我们的代码中M1为奇数会进入第一个if分支逻辑是覆盖的。5.4 乘积溢出问题非 Python 语言在 C 或 Java 中使用int或long long很可能会溢出。有几种处理方式使用大数类如 Java 的BigIntegerC需要自己实现或使用第三方库。取模如果题目要求输出取模后的结果那么可以在乘法过程中每一步都取模。但这完全改变了问题的性质因为取模后数的相对大小关系可能改变我们的贪心策略基于数值比较在取模意义下可能失效。除非题目明确说明“输出取模后的结果”否则不能轻易在贪心过程中取模。使用浮点数取对数比较一个巧妙的技巧是比较a*b和c*d的大小可以转化为比较log|a|log|b|和log|c|log|d|的大小。这样可以避免中间结果溢出但要注意负号的处理和精度问题。对于竞赛这通常不是首选除非万不得已。5.5 构造全面的测试集自己测试时务必覆盖以下场景常规混合[1,2,3,-4,-5], M4- 应得1*2*-4*-540或2*3*-4*-5120我们的算法会选2,3,-4,-5。全正数[5,4,3,2,1], M3-5*4*360。全负数M为偶数[-5,-4,-3,-2,-1], M4- 应选绝对值最大的两对(-5*-4)*(-3*-2)20*6120。全负数M为奇数[-5,-4,-3,-2,-1], M3- 应选绝对值最小的三个-1*-2*-3-6。有零无法组成正数[0, -1, -2], M3- 结果为0。有零但可以组成正数[0, 1, 2, -3, -4], M4- 应选1, 2, -3, -4得24不选零。M 1[-10, -1, 0, 5], M1- 应选5。M N[1, -2, 3, -4], M4- 全部选的乘积为24。6. 算法扩展与同类问题思考解决这道题后我们可以进一步思考一些变种和类似问题这能帮助我们巩固这类贪心问题的求解模式。6.1 变种求最小乘积如果题目改为求“最小乘积”通常指代数值最小即最负的数思路是否完全对称 并不完全。对于最小乘积如果可以选择负数那么目标是让乘积尽可能负或者尽可能小。策略会发生变化可能优先选择绝对值大的正数和负数单配或者成对选择正数如果允许结果为负这需要重新分析。一个实用的方法是求最小乘积可以转化为求“最大乘积”的相反数吗不能直接转因为符号处理不同。更可靠的方法是在排序后考虑几种候选方案选绝对值最大的几个数如果它们能构成负数、或者包含零等。6.2 同类问题模式识别“最大乘积”问题属于“带约束的选取问题”约束是选取个数 M目标是乘积最大。这类问题往往有以下特点序列排序因为乘积对顺序不敏感排序能帮助我们看清结构。分类讨论根据元素符号正、负、零和选取个数 M 的奇偶性情况会截然不同。画决策树是理清思路的好方法。贪心选择基于“当前最优”的选择往往需要证明或至少说服自己局部最优能导致全局最优。常用的证明技术有交换论证、反证法等。边界处理零、全部元素同号、M1、MN 等情况总是代码正确性的杀手。6.3 从本题抽象出的解题框架遇到此类最值问题可以遵循以下步骤定性分析目标函数乘积受哪些因素影响绝对值大小、符号。约束是什么选取个数。数据预处理排序按值、按绝对值。分类正、负、零。寻找贪心策略尝试制定一个基于当前信息的简单决策规则例如优先选绝对值大的正数负数成对选。验证策略用极端例子测试策略全正、全负、有零、M奇偶。思考策略是否可能失败。处理边界专门考虑那些使策略失效的角落情况如奇数 M 无正数。代码实现与测试用清晰的代码实现并运行第 4 步想到的测试用例。这道“最大乘积”题就像一把钥匙打开了一类组合优化贪心问题的大门。它的价值不在于背下一个解法而在于理解其背后的分析过程——如何分解问题、如何处理符号、如何论证贪心、如何小心边界。把这些思路内化再遇到“最大和”、“最小差”或者带权重的变种时你就能更快地找到方向。在竞赛和实际开发中这种结构化思考的能力远比记住十个算法模板更有用。