Intermediate Level
Implement the integerBreakMaximumProduct method that finds the maximum product after splitting an integer into at least two parts.
The input contains an integer n. Your task is to break n into at least two positive integers and return the maximum possible product of those integers.
For example, 10 can be split as 3 + 3 + 4, and the product is 3 * 3 * 4 = 36, which is the maximum result.
Example 1
Input
n (int) =
10Returns (int)
36Example 2
Input
n (int) =
2Returns (int)
1Example 3
Input
n (int) =
8Returns (int)
18Use dynamic programming to test the best product possible for each number from 2 to n.
For a number i, try every first split j. The remaining part is i - j. For each split, choose whether to use the remaining part directly or break it further using the best value already stored in dp.
The answer for n is the largest product found after checking all splits.
Pseudocode:
function integerBreakMaximumProduct(n):
dp = array of n + 1 values filled with 0
for i from 2 to n:
for j from 1 to i - 1:
withoutFurtherBreak = j * (i - j)
withFurtherBreak = j * dp[i - j]
dp[i] = max(dp[i], withoutFurtherBreak, withFurtherBreak)
return dp[n]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run