Intermediate Level
Implement the maximumProductCutting method that finds the maximum product obtainable by cutting an integer into parts.
The input contains an integer n. Your task is to split n into at least two positive integers so that their product is as large as possible.
Return the maximum product after cutting. For example, when n = 10, one best split is 3 + 3 + 4, and the product is 36.
Example 1
Input
n (int) =
2Returns (int)
1Example 2
Input
n (int) =
10Returns (int)
36Example 3
Input
n (int) =
5Returns (int)
6For each number, try every possible first cut.
When cutting n into cut and n - cut, the remaining part can either stay uncut or be cut further. So compare cut * remaining with cut * bestProductOfRemaining.
Dynamic programming stores the best product for each smaller length, which allows larger answers to be built efficiently.
Pseudocode:
function maximumProductCutting(n):
dp = array of n + 1 values filled with 0
for lengthValue from 2 to n:
best = 0
for cut from 1 to lengthValue - 1:
remaining = lengthValue - cut
withoutFurtherCut = cut * remaining
withFurtherCut = cut * dp[remaining]
best = max(best, withoutFurtherCut, withFurtherCut)
dp[lengthValue] = best
return dp[n]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run