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.
def integerBreak(n):
dp = [0] * (n + 1); dp[1] = 1; for i in range(2, n + 1):
max_val = 0; for j in range(1, i):
max_val = max(max_val, max(j * dp[i - j], j * (i - j))); dp[i] = max_val; 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?