LeetCode 343. Integer Break

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.

思路 O(n^2)

注：这题还有O(n)解决的方法，我提交的方法是O(n^2)的。
有点像动态规划的题，上一个数的状态经过乘法可以作为下个数的备选（要与下个数比较）。
假设result[i]存了当前能加到i的最好结果值；
第一遍，从1开始往后加(反正最大的n也就58)，1+1=2，则result[2]中就是1*1=1，1+2=3=>result[3]=1*2=2；result[4]=3
第二遍，从2开始往后加，a[3]=2，a[4]=2*2(原始值为3，这里更新为4),…
…
第五遍，从5开始往后加，但之前算的过程中，result[5]的结果已经被更新成了6，这个数比5大，因此×的时候，被乘数是6而不是5；
以此类推…

思路 O(logn)

需要一点数学思维，详见https://discuss.leetcode.com/topic/42991/o-log-n-time-solution-with-explanation

代码

public class Solution {
    public int max(int x, int y){
        return x>y ? x : y;
    }
    public int integerBreak(int n) {
        int[] result = new int[59]; //0 to 58
        result[1] = 1;  //dummy
        for(int i=1; i<=n-1; i++)
        {
            for(int j=1; j<=n-i; j++)
            {
                int temp = result[i];
                if(result[i] < i)
                    temp = i;
                result[i+j]=max(result[i+j], temp * j);
            }
        }
        return result[n];
    }
}