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.
1class Main {
2 public static int integerBreak(int n) {
3 if (n <= 3) return n - 1;
4 int[] dp = new int[n + 1];
5 dp[2] = 1;
6 dp[3] = 2;
7 for (int i = 4; i <= n; ++i) {
8 for (int j = 1; j < i; ++j) {
9 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
10 }
11 }
12 return dp[n];
13 }
14
15 public static void main(String[] args) {
16 int n = 10;
17 System.out.println("Maximum product for " + n + " is " + integerBreak(n));
18 }
19}This Java program employs a similar logic as the previous solutions. We use an array dp to memoize the optimal solutions of subproblems, building up to the solution of the main problem by checking possible combinations for each split.
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 Python solution utilizes a mathematical method to achieve an efficient result. The integer is repeatedly reduced by factors of 3, ensuring optimal chunks for maximizing the final product.