290. Integer Break
You are given an integer n >= 2. Write it as a sum of at least two positive integers, and choose the parts so that their product is as large as possible. The function receives n and returns that maximum product.
For example, n = 10 does best as 3 + 3 + 4, whose product is 36.
The "at least two parts" rule matters: you are not allowed to keep n in one piece, which is why small inputs can score less than n itself (3 must become 1 + 2 or 2 + 1... best product 2).
Example 1:
Input: n = 2
Output: 1
Explanation: The only split is 1 + 1, so the product is 1 × 1 = 1.
Example 2:
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4 gives 3 × 3 × 4 = 36; no other split beats it.
Constraints:
- 2 ≤ n ≤ 58
- The answer fits in a 64-bit integer (it already crowds the 32-bit ceiling at n = 58).
Hints:
Define best[i] = the maximum product for splitting i. Peel a first part j off i: the remainder i − j can either stay whole (product j·(i−j)) or be split further (product j·best[i−j]). Take the max over all j.
Stare at the optimal splits as n grows — parts of 3 dominate. A part of 5 or more is never optimal (3·(p−3) > p for p ≥ 5), a part of 1 is wasted, and three 2s lose to two 3s (8 < 9). So the answer is all 3s, patched with a 4 or a single 2 depending on n mod 3.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 2
Expected output: 1