Math Dynamic Programming Tabulation
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) = 2
Return:
(int) 1
Example 2
Input:
n (int) = 10
Return:
(int) 36
Example 3
Input:
n (int) = 5
Return:
(int) 6

For 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]
Run your code to see the result.