Integer Break

Problem

Given an integer n >= 2, break it into at least two positive integers and return the maximum product of those parts.

Let dp[i] be the best product for i; for each split j, take the larger of j * (i - j) and j * dp[i - j]. The answer for n is dp[n].

Hint

dp[i - j] already accounts for breaking the remainder further, while j * (i - j) stops after one split.

case 1

in: [2]

expected: 1

case 2

in: [10]

expected: 36

case 3

in: [3]

expected: 2

case 4

in: [4]

expected: 4

case 5

in: [8]

expected: 18

Starter codePython

def integer_break(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor