Integer Break

Problem Statement

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Solution

We are given a clear indication of the way forward in the problem statement: maximum product. Almost exclusively, this means we want to move forward with a DP solution. Some times, you'll encounter a greedy approach that could work but those are typically harder to see up front.

What states are we looking at here, and what are the overlapping subproblems we wish to take advantage of? Well it seems pretty obvious that we wish to compute the maximum product of each number $[0\dots n]$ in order to achieve our final answer. This makes sense intuitively because you would be able to break up $n$ into $\frac{n}{2}$ and if you had already computed that, then it would be trivial.

Implementation-wise, there are some nuances to this tho. For example, what are the base cases? Well we can reason about the first few:

• 1 -> 1
• 2 -> 1
• 3 -> 2

These make sense right? Technically the problem statement invalidates our answer for 1 because you can't split that up into at least 2 positive integers, but thats ok. So if we have this, then, how could we calculate 4? Well, we would want the max product of:

• 3 * 1
• 2 * 2
• 1 * 3

Of course, the last approach is redundant and unnecessary, so we only need to iterate through half of the numbers to find our maximum. Let's reinforce this idea with one more example: 8. We want the maximum of:

• dp[7] * 1
• dp[6] * 2
• dp[5] * 3
• dp[4] * 4

You may be asking, why is only one side of this relying on previously computed results? Well the answer is interesting and a little unclear when first tackling this problem. If we really wanted to crunch the returned value of 8 by hand, we would need to enumerate every single k-sized arrangement of additive factors for 8. This is something that clearly our program does not do, and instead relies on the fact that dp[7] will essentially be reduced into k for k >= 2 factors itself, allowing us to forego this expensive and complex expansion. There is also a subtlety here, let's go back to our example with 4. If we now compute dp[2] * 2, our answer will be 2, not the correct answer of 4As we have already shown, the correct answer for 4 is 4. So is this approach cooked? Not so much, but we do have to bend the contemporary practices of dynamic programming here. For 1,2,3 specifically, we need to allow the later numbers to read a different value for them instead of their true computation. So we need to hardcode:

dp = [-1] * (n+1)
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3

I know this is super annoying and makes zero sense locally, but if you look at it from a global perspective, this allows all of our results to make sense. For example, if we are to compute this program on 5, we would obviously expect an answer of 6, since 3 * 2 = 6. With our approach,

• dp[3] * 2 = 6
• dp[2] * 3 = 6

Clearly these give correct results thru our manipulation of the base cases. Otherwise, we expect every number to play well with the recurrence relation, giving us the final solution reminiscent of an Unbounded Knapsack solution:

if (n <= 3):
	return n - 1
	
dp = [-1] * (n+1)
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3

for i in range(4, n + 1):
	for j in range(1, i):
		dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]))
return dp[-1]