Sponsored
Sponsored
The dynamic programming approach involves creating an array dp where dp[i] represents the maximum product obtainable for the integer i. The idea is to iterate through numbers from 2 to n and for each number, explore all possible ways to split it into two positive integers j and i-j. The solution for each i is derived by taking the maximum of j * (i-j) or j * dp[i-j] for all j from 1 to i-1.
Time Complexity: O(n^2) because of the nested loop iterating through i and j.
Space Complexity: O(n) for the dp array.
1def integerBreak(n):
2 if n <= 3:
3 return n - 1
4 dp = [0] * (n + 1)
5 dp[2], dp[3] = 1, 2
6 for i in range(4, n + 1):
7 for j in range(1, i):
8 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
9 return dp[n]
10
11n = 10
12print(f"Maximum product for {n} is {integerBreak(n)}")This Python solution applies a bottom-up DP approach where dp[i] stores the maximum product obtainable for integer i. The outer loop iterates through numbers from 4 to n, while an inner loop splits i into two parts to find the optimal product.
The mathematical approach relies on the observation that numbers are best broken down into 2s and 3s to maximize their product. In particular, the number 3 plays a critical role. For any number greater than 4, it is beneficial to use as many 3s as possible, because any larger piece can be expressed as 3k + r, where adding more 3s generally yields a larger product (e.g., breaking 4 into 2 + 2 is optimal, compared to using one 3 and a 1). The approach is to keep factoring out 3 from n as long as the remaining part is not less than 4, then multiply the results together to get the maximum product.
Time Complexity: O(log n), as we repeatedly subtract 3.
Space Complexity: O(1) since no extra space is used besides variables.
This C code snippet uses a mathematical approach to solve the integer break problem. Instead of solving it iteratively, we repeatedly factor out 3 from the integer until the remaining integer is less or equal to 4, at which point the product is simply multiplied by the final remainder.