Java 实现
class Solution {
public int integerBreak(int n) {
if (n <= 3) {
return n - 1;
}
int quotient = n / 3; int remainder = n % 3; if (remainder == 0) { return (int) Math.pow(3, quotient); } else if (remainder == 1) { return (int) Math.pow(3, quotient - 1) * 4; } else { return (int) Math.pow(3, quotient) * 2; } }}
思路说明
核心结论：尽可能多地拆出 3。
原因：
- 拆成 1 没有意义，因为 1 × x = x，不会变大；
- 拆成 2 或 3 是有效的；
- 对于大于 3 的数，继续拆总能更大，比如 4 = 2 + 2，2 × 2 = 4；5 = 2 + 3，2 × 3 = 6 > 5；
- 比较 2 × 2 × 2 = 8 和 3 × 3 = 9，可见 3 的乘积增长更快。
所以策略是：
余数 处理方式
0 全部拆成 3
1 拿出一个 3，和 1 合并成 2 + 2，即乘以 4
2 剩下的 2 单独保留
当 n <= 3 时，题目要求至少拆成两个正整数，所以 2 → 1×1=1，3 → 1×2=2，直接返回 n - 1。
复杂度
- 时间复杂度：O(1)
- 空间复杂度：O(1)
面试扩展
如果面试官追问 DP 写法，可以补充：
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
DP 思路是：对每个 i，枚举第一刀拆出 j，剩下 i - j 可以选择不再拆（j × (i-j)）或继续拆（j × dp[i-j]），取最大值。时间复杂度 O(n²)，空间 O(n)。
面试时可以先讲贪心 O(1) 解法，再主动提到 DP 版本作为保底思路，会比较稳。
要不要顺带说说它的变体「整数拆分 II」——把 n 换成字符串形式输入、结果要对 10^9+7 取模的写法？
