【LeetCode】 343. Integer Break

Description

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.

Constraints:

• 2 <= n <= 58

給一整數 n，將他分割成 k 份，其中 k >= 2 且為正整數，最大化這些整數的乘積。
回傳你可能得到的最大乘積。

限制：

• 2 <= n <= 58

Example:

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Solution

• 比較像個數學問題，我們可以從小的數字開始思考
  • 2 只能分成 1 * 1 = 1，沒得選擇
  • 3 的最大值是 1 * 2 = 2
  • 4 的最大值是 2 * 2 = 4
  • 5 的最大值是 2 * 3 = 6
    • 以後遇到剩下 5 的情況，就知道要拆成 2 * 3
  • 6 的最大值是 3 * 3 = 9，而不是 2 * 2 * 2 = 8
    • 以後遇到剩下 6 的情況，就知道要拆成 3 * 3
  • 7 的最大值是 3 * 3 * 2
• 可以發現，原則就是盡量分成 3，但是剩下 4 的時候不能分
  • 4 > 3 * 1
• 另外，2 和 3 本身也是特例，因為一定至少要分成兩份

Code

class Solution {
public:
    int integerBreak(int n) {
        if(n == 2 || n == 3)
            return n - 1;
        if(n % 3 == 0)
            return pow(3, n / 3);
        else if (n % 3 == 1)
            return 4 * pow(3, (n - 4) / 3);
        else
            return 2 * pow(3, (n - 2) / 3);
    }
};

tags: LeetCode C++