343. Integer Break

343. Integer Break

Question

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.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Thinking:

• Method 1: dp

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