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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int integerBreak(int n) {
6 if (n <= 3) return n - 1;
7 vector<int> dp(n + 1, 0);
8 dp[2] = 1;
9 dp[3] = 2;
10 for (int i = 4; i <= n; ++i) {
11 for (int j = 1; j < i; ++j) {
12 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
13 }
14 }
15 return dp[n];
16}
17
18int main() {
19 int n = 10;
20 cout << "Maximum product for " << n << " is " << integerBreak(n) << endl;
21 return 0;
22}In this C++ solution, we use a vector dp to store the maximum products, similar to the C example. For each integer i, we determine the optimal split by iterating through possible splits and updating the value at dp[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.
In this Java solution, we utilize the mathematical pattern that splitting n by extracting factors of 3 results in the largest products for larger values of n. The method stops with the remainder n when it is less than or equal to 4.