0343. 整数拆分【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学贪心

1. 📝 题目描述

• leetcode

给定一个正整数 n，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积。

---

示例 1：

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2：

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

---

提示：

• 2 <= n <= 58

2. 🎯 s.1 - 数学贪心

c

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

js

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function (n) {
  if (n <= 3) return n - 1
  const q = Math.floor(n / 3),
    r = n % 3
  if (r === 0) return 3 ** q
  if (r === 1) return 3 ** (q - 1) * 4
  return 3 ** q * 2
}

py

class Solution:
    def integerBreak(self, n: int) -> int:
        if n <= 3:
            return n - 1
        q, r = divmod(n, 3)
        if r == 0:
            return 3 ** q
        if r == 1:
            return 3 ** (q - 1) * 4
        return 3 ** q * 2

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

算法思路：

• 尽可能拆成 3，因为 $3\times 3>2\times 2\times 2$
• 余数为 0 直接返回 $3^q$，余 1 则拆一个 3 出来凑成 $4$，余 2 则乘 $2$