For 10 we can have the following:
1+9, 2+8, 3+7, 4+6, 5+5
Since we know we want to maximize the total product, there is overlapping subproblem, as maximizing the product of 9 will help us maximize the total product of 1 * 9.
Therefore we can derive the recurrence relationship:
res = max(factor2, dp[factor2]) * max(factor1, dp[factor1])
def integerBreak(self, n): dp = [0 for i in range(n+1)] for num in range(2, n+1): for addend in range(1, num/2+1): res = max(addend, dp[addend]) * max(num-addend, dp[num-addend]) dp[num] = max(dp[num], res) return dp[n]