Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an integer n, find two or more integers such that their sum is equal to n, where the product of these integers is maximized, and return this product.
Constraints
n ≤ 100,000
Example 1
Input
n = 11
Output
54
Explanation
3 + 3 + 3 + 2 = 11 and 3 * 3 * 3 * 2 = 54Hint #1
What is the least to which you can split the number that gives you the maximum value?
Greedy Alorithm to Split Maximum Product
The best/optimal strategy is to split into 3 if it can. For example, given 6, the best is to split as 3+3 which has 3*3=9 other than, 2+2+2 (product 8) or 4+2 (product 8), 5+1 (product 5) etc. Thus, we can repeatedly split into 3 – and if it is less or equal 4, we multiply it.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def maxIntegerBreakProduct(self, n): if n == 1 or n == 2: return 1 if n == 3: return 2 ans = 1 while n > 4: ans *= 3 n -= 3 return ans * n |
class Solution: def maxIntegerBreakProduct(self, n): if n == 1 or n == 2: return 1 if n == 3: return 2 ans = 1 while n > 4: ans *= 3 n -= 3 return ans * n
The time complexity is O(N). The space complexity is O(1) constant.
Max Integer Split Product by Top Down Dynamic Programming Algorithm
The DP (Dynamic Programming) Equaltion is:
for i between 1 to n – 1 inclusive. The terminal conditions are and
The top down Dynamic Programming can be implemented using Recursion with Memoization.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def maxIntegerBreakProduct(self, n): @cache def f(n): if n == 1 or n == 2: return 1 ans = 1 for i in range(1, n): ans = max(i * (n - i), i * f(n - i), ans) return ans return f(n) |
class Solution: def maxIntegerBreakProduct(self, n): @cache def f(n): if n == 1 or n == 2: return 1 ans = 1 for i in range(1, n): ans = max(i * (n - i), i * f(n - i), ans) return ans return f(n)
Time complexity is O(N^2) and the space complexity is O(N).
This is Top-down DP as we are calculating DP(n) and that requires DP(n-1), DP(n-2) etc..
Split Integer to Get Maximum Product via Bottom-up Dynamic Programming Algorithm
We can implement the DP in the reverse direction aka bottom-up fashion where we store the intermediate DP values in an array/list.
1 2 3 4 5 6 7 | class Solution: def maxIntegerBreakProduct(self, n): dp = [1] * (n + 1) for i in range(1, n + 1): for j in range(1, i): dp[i] = max(dp[i], j * (i - j), j * dp[i - j]) return dp[-1] |
class Solution: def maxIntegerBreakProduct(self, n): dp = [1] * (n + 1) for i in range(1, n + 1): for j in range(1, i): dp[i] = max(dp[i], j * (i - j), j * dp[i - j]) return dp[-1]
Time complexity is O(N^2) and the space complexity is O(N). This is usually faster than top-down DP because that no recursion is needed (saving the function calls). The DP values are calculated from DP[1], DP[2] .. until DP[n].
See also: Greedy Algorithm to Maximize the Split Product (Integer Break)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: A Simple Fork Bomb in C++
Next Post: Two PHP Functions to Check HTTP Response Code (Status) of a URL using Curl