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.
1function integerBreak(n) {
2 if (n <= 3) return n - 1;
3 let dp = Array(n + 1).fill(0);
4 dp[2] = 1;
5 dp[3] = 2;
6 for (let i = 4; i <= n; ++i) {
7 for (let j = 1; j < i; ++j) {
8 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
9 }
10 }
11 return dp[n];
12}
13
14let n = 10;
15console.log(`Maximum product for ${n} is ${integerBreak(n)}`);In this JavaScript implementation, we follow the same dynamic programming pattern as previously described. An array dp is used to store maximum products for subproblems, with nested loops exploring all possible number splits to compute dp[i] for each i.
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.
The JavaScript code implements the mathematical approach by breaking down the number n into factors of 3, accumulating the product, and handling the remainder once n is sufficiently small.