408. Break It For the Largest Product
Split n into AT LEAST TWO positive whole numbers that add up to n, and
print the largest product those parts can have.
2 -> 1 1 + 1
10 -> 36 3 + 3 + 4
The "at least two" is not decoration: without it the answer would always be n
itself, taken as a single part.
The recurrence needs one careful line. Having chosen a first part j, the rest
n - j may either be left whole or broken further, and both must be considered:
dp[i] = max over j in 1..i-1 of max( j * (i - j), j * dp[i - j] )
Writing only j * dp[i-j] is the usual error. It forces the remainder to be
split too, and since dp[i] is defined as needing two or more parts, it forbids
the answer 3 * 4 for n = 7 and returns 9 instead of 12.
Once the table is built, a pattern appears: the parts are almost all 3s, with a 4 or a pair of 2s when the remainder demands it. That is provable, and it gives a constant-time solution. Deriving it from the table is a better use of the problem than being told it.
Constraints - `2 ≤ n ≤ 100` - The answer fits in a signed 64-bit integer.
Input
One line containing the integer n.
Output
Print the largest product obtainable by splitting n into two or more positive parts.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.