# 【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++`