A rope of integer length n must be cut into at least two pieces of positive integer length. The pieces are then sold for a price equal to the product of their lengths. Return the largest price obtainable.
Examples
Input: n = 10
Output: 36
Explanation: 3 + 3 + 4 = 10 and 3 * 3 * 4 = 36.
Input: n = 2
Output: 1
Explanation: the only cut is 1 + 1.
Constraints
2 <= n <= 1000- Target complexity: O(n^2) time (an O(n) or O(1) arithmetic solution is also fine).
Goals
- Maximise a product over all ways to split an integer
- Handle the requirement of at least two pieces separately from the recurrence