343. Integer Break - jiejackyzhang/leetcode-note GitHub Wiki

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 and not larger than 58.

##Approach 1: O(n) 首先观察到当n = 2或3时，拆分后没有原来大，而n = 4时，拆分后和原来一样大。 因此当拆分的值大于4时，继续拆分，而拆分后的值小于4时，则不必拆分了。 因此，最终的数可拆分为一堆2和3的组合，可以证明尽量多的3可使最终的乘积最大。

public class Solution {
    public int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n == 4) return 4;
        return 3 * Math.max(n-3, integerBreak(n-3));
    }
}

public class Solution {
    public int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int res = 1;
        while(n > 4) {
            n -= 3;
            res *= 3;
        }
        if(n == 2) return 2*res;
        else if(n == 3) return 3*res;
        else return 4*res;
    }
}

##Approach 2: Dynamic Programming 令dp[i]表示i拆分成至少两个数字的最大的乘积，则

dp[i] = max{max(j, dp[j]) * max(i-j, dp[i-j])} for all j < i

public class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i-j, dp[i-j]));
            }
        }
        return dp[n];
    }
}