343. Integer Break

Q:

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.

A:


 就是按照3 来区分。 主要是 * 3 比  *2 要给出更多product。 而且sum里损失的也少。

public class Solution {
    public int integerBreak(int n) {
        return helper(n,true); 
    }
    public int helper(int n, boolean isMustDecode){
        if( n<=3 ){
            return isMustDecode? n-1 : n;
        }
        // we only care about 2 and 3 as potential decoposation
        if(n>4)
            return 3*helper(n-3, false);
        else if(n == 3 )
            return 3 ;
        else // n == 4 or 2 or 1
            return n;
    }
}