mediumDynamic Programming 1DPure DSA~25 min
Break an Integer to Maximize the Product of Its Parts
Split a capacity n into a sum of at least two positive integers so that the product of those parts is as large as possible.
Problem
Given an integer n, break it into the sum of k positive integers with k >= 2, and maximize the product of those integers. Return the maximum product obtainable.
Input
A single integer n.
Output
An integer: the maximum product of the parts.
Constraints
- 2 <= n <= 58
- At least two parts are required.
- Parts are positive integers.
Examples
Example 1
Input
n = 2
Output
1
2 = 1 + 1, product 1.
Example 2
Input
n = 10
Output
36
10 = 3 + 3 + 4, product 36.