Teaching Kids Programming – Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm


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 = 54

Hint #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:

tex_949af9149e3182222ab7498819a275ed Teaching Kids Programming - Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm algorithms dynamic programming math teaching kids programming youtube video for i between 1 to n – 1 inclusive. The terminal conditions are tex_c4ec2575b1c9bae6f84cbbf914ebaef8 Teaching Kids Programming - Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm algorithms dynamic programming math teaching kids programming youtube video and tex_e05fefefa8d559dbd4453ad2798c0cb1 Teaching Kids Programming - Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm algorithms dynamic programming math teaching kids programming youtube video

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) —

GD Star Rating
loading...
656 words
Last Post: A Simple Fork Bomb in C++
Next Post: Two PHP Functions to Check HTTP Response Code (Status) of a URL using Curl

The Permanent URL is: Teaching Kids Programming – Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm

Leave a Reply