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.

Ideas:

DP: 外循环i从2到n，内循环j从1到i 看之前结果dp[j]与j谁大，dp[i-j]与i-j谁大，取大的相乘，并找dp[i]最大值

Code:

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; 2*j <= i; j ++) {
            dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
        }
    }
    return dp[n];
}