DSA problem
Integer Break
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.
This is a clean 1-D DP problem. Define dp[i] as the maximum product obtainable by breaking the integer i into at least two positive integer parts. To compute dp[i], try every first cut j from 1 to i - 1. After cutting off j, the remainder i - j may itself be left intact (contributing i - j to the product) or further broken (contributing dp[i - j]). Likewise for j — but since j < i it's always cleaner to take max(j, dp[j]). The recurrence:
dp[i] = max over j in [1, i - 1] of max(j, dp[j]) * max(i - j, dp[i - j]).
A direct O(n^2) tabulation works fine for the given constraints. There is also a clever O(n) math observation: the optimal break is to use as many 3's as possible (with 2's filling in when n mod 3 != 0), because 3 maximizes the geometric-mean trade-off. For interview rigor we show the DP solution; the math identity is mentioned in the hints.
The DP runs in O(n^2) time and O(n) space, which is well within the constraints 2 <= n <= 58.
Examples
n = 21n = 1036n = 818Constraints
- 2 <= n <= 58
- You must break n into at least two positive integer parts.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.