Integer Break

LeetCode Q 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.

Solution

DP function:
dp[n] = Max{ Max(dp[i], i) * Max(dp[n - i], n - i) }, i < n

Time Complexity: O(n^2)
Space Complexity: O(n)

---

Code:

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