企业官网建设流程全解析

Hello 算法贪心章：最大切分乘积问题的完整推导与多语言实现

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇技术指南聚焦《Hello 算法》（hello-algo）贪心章节中的最大切分乘积问题：给定正整数 n，将其切分为至少两个正整数之和，求所有因子乘积的最大值。文中将完整复现贪心策略的数学推导（为何最终只出现因子 2 与 3、为何"三个 2 换两个 3"）、给出基于整除与取模的 O(1) 级代码实现，并结合仓库中 Python、Java、C、C++、Go、Rust、TypeScript 等 14 种语言的源码，剖析不同语言在幂运算上的实现差异与边界处理。读完后，你将掌握一个"贪心策略证明 + 数学优化消去循环"的完整范例，并能在各语言环境下直接运行验证。

问题定义

给定一个正整数 $n$，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少。

假设将 $n$ 切分为 $m$ 个整数因子，其中第 $i$ 个因子记为 $n_i$，即

$$ n = \sum_{i=1}^{m} n_i $$

本题的目标是求得所有整数因子的最大乘积，即

$$ \max \left( \prod_{i=1}^{m} n_i \right) $$

需要回答的两个核心问题：切分数量 $m$ 应该多大？每个 $n_i$ 应该是多少？

贪心策略一：大于等于 4 的因子都应继续切分

根据经验，两个整数的乘积往往比它们的加和更大。假设从 $n$ 中分出一个因子 $2$，则它们的乘积为 $2(n-2)$。将该乘积与 $n$ 作比较：

$$ \begin{aligned} 2(n-2) & \geq n \ 2n - n - 4 & \geq 0 \ n & \geq 4 \end{aligned} $$

当 $n \geq 4$ 时，切分出一个 $2$ 后乘积会变大，这说明大于等于 $4$ 的整数都应该被切分。

贪心策略一：如果切分方案中包含 $\geq 4$ 的因子，那么它就应该被继续切分。最终的切分方案只应出现 $1$、$2$、$3$ 这三种因子。

贪心策略二：因子 3 比 2 更优，最多保留两个 2

在 $1$、$2$、$3$ 三个候选因子中，显然 $1$ 是最差的，因为 $1 \times (n-1) < n$ 恒成立，切分出 $1$ 反而会导致乘积减小。

进一步比较 $2$ 与 $3$：当 $n = 6$ 时，有 $3 \times 3 > 2 \times 2 \times 2$，这意味着切分出 $3$ 比切分出 $2$ 更优。

贪心策略二：在切分方案中，最多只应存在两个 $2$。因为三个 $2$ 总是可以替换为两个 $3$（$2 \times 2 \times 2 = 8 < 9 = 3 \times 3$），从而获得更大的乘积。

最终贪心策略

综合以上两条推理，可导出可直接执行的贪心策略：

1. 输入整数 $n$，从其不断切分出因子 $3$，直至余数为 $0$、$1$、$2$；
2. 当余数为 $0$ 时，代表 $n$ 是 $3$ 的倍数，不做任何处理；
3. 当余数为 $2$ 时，不继续划分，保留该 $2$；
4. 当余数为 $1$ 时，由于 $2 \times 2 > 1 \times 3$，应将最后一个 $3$ 和余数 $1$ 替换为两个 $2$。

代码实现：用整除与取模消去循环

按上述策略，无须通过循环反复切分整数。利用向下整除运算得到 $3$ 的个数 $a$，用取模运算得到余数 $b$，此时有：

$$ n = 3a + b $$

特别注意边界情况：当 $n \leq 3$ 时，题目要求至少切分为两个正整数，因此必须拆分出一个 $1$，乘积为 $1 \times (n - 1)$。

仓库中各语言实现的算法主体完全一致。以 Python 实现 为例：

def max_product_cutting(n: int) -> int: """最大切分乘积：贪心""" # 当 n <= 3 时，必须切分出一个 1 if n <= 3: return 1 * (n - 1) # 贪心地切分出 3 ，a 为 3 的个数，b 为余数 a, b = n // 3, n % 3 if b == 1: # 当余数为 1 时，将一对 1 * 3 转化为 2 * 2 return int(math.pow(3, a - 1)) * 2 * 2 if b == 2: # 当余数为 2 时，不做处理 return int(math.pow(3, a)) * 2 # 当余数为 0 时，不做处理 return int(math.pow(3, a))

各分支与贪心策略一一对应：余数 $b=1$ 时，$a$ 个 $3$ 中拿出一个与余数 $1$ 合并为 $2 \times 2$，乘积为 $3^{a-1} \times 4$；$b=2$ 时保留余数，乘积为 $3^a \times 2$；$b=0$ 时乘积即 $3^a$。

多语言源码对照

同一算法在仓库各语言目录下的实现保持了统一结构（边界判断 → 求 $a$、$b$ → 按余数分支），差异集中在幂运算的调用方式上：

这种差异并非随意选择，而是直接对应下一节的复杂度分析：浮点幂（C 库pow系）与整数幂（如 Rust 的pow）的开销模型不同。

驱动代码与测试用例

各语言的 Driver Code 统一取 $n = 58$。以 Go 为例，max_product_cutting.go 的main与 测试文件 max_product_cutting_test.go 均调用maxProductCutting(58)并打印"最大切分乘积"。从源码结构看，$58 = 3 \times 19 + 1$，命中余数为 $1$ 的分支，结果为 $3^{18} \times 4 = 1,549,681,956$，恰好落在 32 位有符号整数范围内（$< 2^{31}-1$）——这也解释了为何 C、Java、Go 等以int返回的实现可以安全地使用该测试值。

在 Python 环境中可直接运行验证：

python codes/python/chapter_greedy/max_product_cutting.py # 输出：最大切分乘积为 1549681956

Go 目录下则可使用其自带测试：

cd codes/go && go test ./chapter_greedy/ -run TestMaxProductCutting

时间复杂度与空间复杂度

时间复杂度取决于编程语言的幂运算的实现方法。以 Python 为例，常用的幂计算方式有三种：

• 运算符**和内置函数pow()的时间复杂度均为 $O(\log a)$（采用快速幂）；
• 函数math.pow()内部调用 C 语言库的pow()函数，执行浮点取幂，时间复杂度为 $O(1)$。

仓库的 Python 实现正是采用math.pow()，因此整体时间复杂度为 $O(1)$；而 Rust 实现采用的整数幂3_i32.pow(...)则对应 $O(\log a)$ 级别的取幂开销（指数本身很小，实际差异可忽略）。

变量 $a$ 和 $b$ 使用常数大小的额外空间，因此空间复杂度为 $O(1)$。

正确性证明（反证法）

只分析 $n \geq 4$ 的情况，假设存在比贪心方案更优的切分，逐项推导矛盾：

1. 所有因子都不大于 3：假设最优切分方案中存在 $\geq 4$ 的因子 $x$，那么一定可以将其继续划分为 $2 \times (x - 2)$，从而获得更大（或相等）的乘积，这与"最优"假设矛盾；
2. 切分方案不包含 1：假设最优切分方案中存在一个因子 $1$，那么它一定可以合并入另外一个因子中（$1 \times y < (1 + y)$），以获得更大的乘积，矛盾；
3. 切分方案最多包含两个 2：假设最优切分方案中包含三个 $2$，那么一定可以替换为两个 $3$（$8 < 9$），乘积更大，矛盾。

三条性质共同锁定：最优方案只由若干个 $3$ 和至多两个 $2$ 组成——这与前面推导出的贪心策略完全一致，从而证明了算法的正确性。

小结

最大切分乘积问题展示了贪心算法的标准解题管线：先通过不等式排除次优因子（策略一），再比较候选因子优劣（策略二），最后用 $n = 3a + b$ 的整数除法把"逐步切分"压缩为常数时间的三个分支。仓库 贪心章节 中的 问题原文 与上述 14 种语言的对照实现（位于codes/<语言>/chapter_greedy/目录下），可作为进一步阅读与运行的起点。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo