All problems

Integer Break

Medium · dynamic programming

You have a ribbon whose length is a whole number n. Cut it into at least two pieces, where every piece has a whole number length of at least 1. The lengths of the pieces must add up to n.

Multiply the lengths of all the pieces together. Return the largest product you can get.

Examples

Example 1

Input: n = 2

Output: 1

The only way to cut it is 1 + 1, and 1 * 1 = 1.

Example 2

Input: n = 6

Output: 9

Cutting into 3 + 3 gives 9. Cutting into 2 + 2 + 2 gives only 8.

Example 3

Input: n = 10

Output: 36

3 + 3 + 4 gives 36.

Constraints

• 2 <= n <= 58