Maximum Product After Integer Break

Problem Description

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

For example:

• If n = 2, the answer is 1 because 2 = 1 + 1 and 1 * 1 = 1
• If n = 10, the answer is 36 because 10 = 3 + 3 + 4 and 3 * 3 * 4 = 36.

Naive Approach (Recursion)

A straightforward approach is to use recursion to explore all possible ways to break the integer n. We can iterate from i = 1 to n - 1, considering i as the first integer in the sum. The remaining part is n - i, which can be further broken down recursively. We keep track of the maximum product found so far.

def integer_break_recursive(n):
    if n <= 1:
        return 1

    max_product = 0
    for i in range(1, n):
        max_product = max(max_product, i * integer_break_recursive(n - i))
    return max_product

def solve(n):
    if n == 2:
        return 1
    return integer_break_recursive(n)

Time Complexity: O(2^n) (Exponential due to overlapping subproblems)

Space Complexity: O(n) (Due to the recursion depth)

Optimal Approach (Dynamic Programming)

Since the recursive approach has overlapping subproblems, we can optimize it using dynamic programming. We can create a dp array where dp[i] stores the maximum product obtainable by breaking the integer i.

1. Base Case: dp[1] = 1 (This is useful for building our solution. It doesn't violate the k >= 2 constraint because it is not the final result, but an intermediate result used to derive the final result).
2. Iteration: For each i from 2 to n, iterate from j = 1 to i - 1. At each step, we have two choices:
   • Don't break i-j down. The product will be j * (i - j).
   • Break i-j down. The product will be j * dp[i - j]. Take the maximum of these and store as the solution.
3. The answer is stored in dp[n].

def integer_break_dp(n):
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        for j in range(1, i):
            dp[i] = max(dp[i], j * (i - j), j * dp[i - j])

    return dp[n]

def solve(n):
    if n == 2:
        return 1
    return integer_break_dp(n)

Time Complexity: O(n^2)

Space Complexity: O(n)

Optimal Approach (Mathematical/Greedy)

Through mathematical analysis, it can be shown that the maximum product is obtained by breaking n into as many 3's as possible. The only exceptions are when n = 2 or n = 4. When n = 4, you should split it into two 2s (2 * 2 = 4), not one 3 and one 1 (3 * 1 = 3).

1. If n == 2, return 1.
2. If n == 3, return 2.
3. If n == 4, return 4.
4. Otherwise, calculate the number of 3's and the remaining part.

def integer_break_math(n):
    if n == 2:
        return 1
    if n == 3:
        return 2
    if n == 4:
        return 4

    product = 1
    while n > 4:
        product *= 3
        n -= 3

    product *= n
    return product

def solve(n):
    return integer_break_math(n)

Time Complexity: O(n) in the worst case (when there is only a single while loop).

Space Complexity: O(1)

Edge Cases

• n = 2: The optimal split is 1 + 1, and the product is 1.
• n = 3: The optimal split is 1 + 2, and the product is 2.
• n = 4: The optimal split is 2 + 2, and the product is 4 (not 3+1 because that yields 3).

Code (Optimal - Mathematical)

def integer_break(n):
    if n == 2:
        return 1
    if n == 3:
        return 2
    if n == 4:
        return 4

    product = 1
    while n > 4:
        product *= 3
        n -= 3

    product *= n
    return product