Integer Break
Given an integer n, break it into the sum of k numbers such that the product of those numbers is maximized. For example, if n = 4, then the optimal solution is 2 + 2, since 2 * 2 = 4, which is larger than 1 + 3 or 1 + 1 + 1 + 1.
Constraints:
- 2 <= n <= 10^5
Examples:
Input: 2
Output: 1
Explanation: The optimal solution is 1 + 1, since 1 * 1 = 1, which is the maximum product that can be achieved.
Input: 10
Output: 36
Explanation: The optimal solution is 3 + 3 + 4, since 3 * 3 * 4 = 36, which is the maximum product that can be achieved.
Solutions
Dynamic Programming
The dynamic programming approach involves creating a table dp where dp[i] represents the maximum product that can be achieved by breaking the integer i into the sum of k numbers. The table is filled in a bottom-up manner, starting from dp[1] = 1. For each i, we try all possible ways to break it into two numbers j and i - j, and update dp[i] with the maximum product that can be achieved.
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[1] = 1;
for (int i = 2;
i <= n;
i++) {
int max = 0;
for (int j = 1;
j < i;
j++) {
max = std::max(max, std::max(j * dp[i - j], j * (i - j)));
}
dp[i] = max;
}
return dp[n];
}Follow-up:
What if the input integer n is very large, and we need to find the maximum product in O(log n) time complexity?
