Write a function `integer_break(n)` that takes a positive integer `n` (where 2 ≤ n ≤ 58) and returns the maximum product you can get by breaking `n` into the sum of at least two positive integers. The order of the parts does not matter, and you must use at least two parts (i.e., you cannot take the number as a single part). For example, for n = 10, the optimal split is 3 + 3 + 4, whose product is 36, so the function returns 36.
Constraints
2 ≤ n ≤ 58. The answer fits in a 32-bit signed integer. Your solution should be efficient enough for n ≤ 58, ideally O(n²) dynamic programming or O(1) math observation.
Think about breaking n into two parts i and n-i, then decide whether to further break those parts.
Store the maximum product for every integer from 1 to n in an array.
For each i from 2 to n, try all splits i = j + (i-j) and take the maximum over j * max(j, dp[j])? Actually, consider the best of j * (i-j), j * dp[i-j], dp[j] * (i-j), dp[j] * dp[i-j]. But note dp[j] already considers breaking j into at least two parts; so the maximum for i is max over j of max(j, dp[j]) * max(i-j, dp[i-j]) but ensure at least one split? Since n≥2, dp[n] will use at least one split because we consider j + (i-j) directly.
Alternatively, observe that for optimality you mostly use 3s, with special cases for remainders 1 or 2. But the DP approach is straightforward.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.