343. Integer Break -- Avota

問題描述:

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

解題思路:

給定一個正整數n(其實後來測試發現n到了59其結果就超出int的表示範圍了)，將其拆解成至少兩個正整數的和，計算拆解數的乘積，找出所能獲得的最大乘積。這種輸入某個數求取某種最好解的題目最簡單有效的方法就是多列幾個例子看看是否有規律，對於這題我們先列出4到12的結果看看：

仔細觀察拆解結果與n模3對應關係，發現餘數為0時最大乘積為3的n/3次冪，餘數為1時最大乘積為4乘以3的（n/3-1）次冪，餘數為2時最大乘積為2乘以3的n/3次冪。

示例代碼:

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