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.
1using System;
2
3public class Solution {
4 public int IntegerBreak(int n) {
5 if (n <= 3) return n - 1;
6 int[] dp = new int[n + 1];
7 dp[2] = 1;
8 dp[3] = 2;
9 for (int i = 4; i <= n; ++i) {
10 for (int j = 1; j < i; ++j) {
11 dp[i] = Math.Max(dp[i], Math.Max(j * (i - j), j * dp[i - j]));
12 }
13 }
14 return dp[n];
15 }
16
17 public static void Main(string[] args) {
18 int n = 10;
19 Console.WriteLine("Maximum product for " + n + " is " + new Solution().IntegerBreak(n));
20 }
21}This C# program uses an iterative method with dynamic programming to solve integer breaks. It initializes the dp array for base cases and iteratively fills it up for all integers up to n by determining optimal sub-splits.
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.