C++求解最大乘积拆分问题

题目描述

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回可以获得的最大乘积。

例如:

• 输入: 6- 输出: 9- 解释: 6 可以拆分为 2 + 2 + 2, 2 * 2 * 2 = 8- 6 也可以拆分为 3 + 3, 3 * 3 = 9，乘积最大。

算法思路

贪心算法可以解决这个问题。 核心思想是尽可能多地拆分出数字 3，因为 3 的乘积增长速度最快。

1. 如果 n 小于等于 3，直接返回 n - 1。2. 如果 n 对 3 取余为 0，则将 n 全部拆分为 3。3. 如果 n 对 3 取余为 1，则拆出一个 4，剩下的全部拆分为 3。4. 如果 n 对 3 取余为 2，则拆出一个 2，剩下的全部拆分为 3。

C++代码实现cpp#include #include using namespace std;

int maxProduct(int n) { if (n <= 3) { return n - 1; } if (n % 3 == 0) { return pow(3, n / 3); } else if (n % 3 == 1) { return pow(3, (n - 4) / 3) * 4; } else { return pow(3, (n - 2) / 3) * 2; }}

int main() { int n; cin >> n; int result = maxProduct(n); cout << result << endl; return 0;}

代码解释

• maxProduct(int n) 函数计算最大乘积。- 使用 if-else 语句根据 n 对 3 的余数进行不同的拆分操作。- pow(3, x) 计算 3 的 x 次方。

示例

输入：10

输出：36

解释：10 可以拆分为 3 + 3 + 4，3 * 3 * 4 = 36。

总结

本文使用贪心算法解决了最大乘积拆分问题，并提供了C++代码实现。该算法时间复杂度为O(1)，空间复杂度为O(1)。