Problem Description

You are given a positive integer n. Your task is to break it into the sum of at least 2 positive integers and maximize the product of those integers.

For example, if n = 10, you could break it into:

• 2 + 8 with product 2 × 8 = 16
• 3 + 7 with product 3 × 7 = 21
• 2 + 3 + 5 with product 2 × 3 × 5 = 30
• 3 + 3 + 4 with product 3 × 3 × 4 = 36

Among all possible ways to break n, you need to find the maximum possible product.

The solution uses dynamic programming where f[i] represents the maximum product obtainable by breaking integer i. For each number i from 2 to n, we try all possible ways to split it into two parts: j and i-j where j ranges from 1 to i-1.

For each split, we have two choices:

1. Don't further break i-j, giving us product (i-j) × j
2. Further break i-j optimally, giving us product f[i-j] × j

We take the maximum among these options and the current value of f[i]: f[i] = max(f[i], f[i-j] × j, (i-j) × j)

The final answer is f[n], which gives the maximum product for breaking integer n.

Intuition

The key insight is that when we break a number n, we're essentially making a decision about how to split it optimally. This naturally leads us to think about dynamic programming since the optimal solution for n depends on optimal solutions for smaller numbers.

Let's think about breaking a number i. We can split it into two parts: some number j and the remainder i-j. Now here's the crucial observation - once we take out j, we have two choices for the remaining part i-j:

1. Keep i-j as is (don't break it further)
2. Break i-j optimally (which we might have already computed for smaller values)

Why these two choices? Because sometimes it's better to keep a number whole rather than breaking it. For instance, if we have the number 4, breaking it into 2 + 2 gives us a product of 4, but keeping it as 1 + 3 and not breaking the 3 gives us 1 × 3 = 3. However, breaking 4 into 2 + 2 gives the maximum product of 4.

This recursive nature suggests we can build up our solution from smaller numbers to larger ones. For each number i, we try all possible "last splits" (taking out j where j goes from 1 to i-1), and for each split, we consider both options: further breaking or not breaking the remainder.

The formula f[i] = max(f[i], f[i-j] × j, (i-j) × j) captures this perfectly:

• f[i-j] × j: the product when we optimally break i-j and multiply by j
• (i-j) × j: the product when we don't break i-j further

By trying all possible values of j and taking the maximum, we ensure we find the optimal way to break each number, building up from smaller values to finally reach our answer for n.

Solution Approach

We implement the solution using dynamic programming with a bottom-up approach. Here's how the algorithm works:

Data Structure:

• We create an array f of size n + 1 where f[i] stores the maximum product obtainable by breaking integer i
• Initialize all values to 1 since the minimum product for any positive integer is 1

Algorithm Steps:

1. Base Case: f[1] = 1 (already set during initialization)

2. Iteration: For each integer i from 2 to n:

   • Try all possible ways to split i into two parts
   • For each possible split position j from 1 to i-1:
     • Calculate the product when we split i into j and i-j
     • We have two options for the remainder i-j:
       • Don't break it further: product = (i - j) × j
       • Break it optimally: product = f[i - j] × j
     • Update f[i] with the maximum of current value and both options

3. State Transition Equation:

   f[i] = max(f[i], f[i - j] × j, (i - j) × j)

   where j ∈ [1, i)

Implementation Details:

f = [1] * (n + 1)  # Initialize DP array
for i in range(2, n + 1):  # Build up from 2 to n
    for j in range(1, i):  # Try all split positions
        f[i] = max(f[i], f[i - j] * j, (i - j) * j)
return f[n]  # Return the maximum product for n

Time Complexity: O(n²) - We have two nested loops, outer loop runs n-1 times and inner loop runs up to i-1 times.

Space Complexity: O(n) - We use an array of size n + 1 to store the DP values.

The algorithm ensures we find the globally optimal solution by considering all possible ways to break each number and building upon previously computed optimal solutions for smaller numbers.

Example Walkthrough

Let's walk through the algorithm with n = 6 to see how we find the maximum product.

Initialization:

• Create array f = [1, 1, 1, 1, 1, 1, 1] (indices 0 to 6)
• f[i] will store the maximum product for integer i

Building the DP table:

i = 2:

• j = 1: Split 2 into 1 and 1
  • Don't break 1: (2-1) × 1 = 1 × 1 = 1
  • Break 1 optimally: f[1] × 1 = 1 × 1 = 1
  • f[2] = max(1, 1, 1) = 1

i = 3:

• j = 1: Split 3 into 1 and 2
  • Don't break 2: (3-1) × 1 = 2 × 1 = 2
  • Break 2 optimally: f[2] × 1 = 1 × 1 = 1
  • f[3] = max(1, 2, 1) = 2
• j = 2: Split 3 into 2 and 1
  • Don't break 1: (3-2) × 2 = 1 × 2 = 2
  • Break 1 optimally: f[1] × 2 = 1 × 2 = 2
  • f[3] = max(2, 2, 2) = 2

i = 4:

• j = 1: Split 4 into 1 and 3
  • Don't break 3: (4-1) × 1 = 3 × 1 = 3
  • Break 3 optimally: f[3] × 1 = 2 × 1 = 2
  • f[4] = max(1, 3, 2) = 3
• j = 2: Split 4 into 2 and 2
  • Don't break 2: (4-2) × 2 = 2 × 2 = 4
  • Break 2 optimally: f[2] × 2 = 1 × 2 = 2
  • f[4] = max(3, 4, 2) = 4
• j = 3: Split 4 into 3 and 1
  • Don't break 1: (4-3) × 3 = 1 × 3 = 3
  • Break 1 optimally: f[1] × 3 = 1 × 3 = 3
  • f[4] = max(4, 3, 3) = 4

i = 5:

• j = 1: f[5] = max(1, 4, 3) = 4
• j = 2: f[5] = max(4, 6, 4) = 6
• j = 3: f[5] = max(6, 6, 4) = 6
• j = 4: f[5] = max(6, 4, 3) = 6

i = 6:

• j = 1: f[6] = max(1, 5, 6) = 6
• j = 2: f[6] = max(6, 8, 6) = 8
• j = 3: f[6] = max(8, 9, 6) = 9
• j = 4: f[6] = max(9, 8, 6) = 9
• j = 5: f[6] = max(9, 6, 4) = 9

Final DP array: f = [1, 1, 1, 2, 4, 6, 9]

Answer: f[6] = 9

This corresponds to breaking 6 into 3 + 3, which gives product 3 × 3 = 9. The algorithm found this by trying the split at j = 3, where we get (6-3) × 3 = 3 × 3 = 9.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²) because there are two nested loops: the outer loop runs from 2 to n (which is n-1 iterations), and for each iteration i, the inner loop runs from 1 to i-1 (which is up to i-1 iterations). The total number of operations is approximately 1 + 2 + 3 + ... + (n-1) = (n-1) × n / 2, which simplifies to O(n²).

The space complexity is O(n) because the algorithm uses a single array f of size n+1 to store the dynamic programming results. No additional space that scales with input size is used beyond this array.

Common Pitfalls

Pitfall 1: Forgetting to Consider Not Breaking Further

The Problem: A common mistake is only considering dp[num - j] * j in the state transition, forgetting that sometimes it's better to keep (num - j) as a single number rather than breaking it further.

Incorrect Code:

for num in range(2, n + 1):
    for j in range(1, num):
        dp[num] = max(dp[num], dp[num - j] * j)  # Missing (num - j) * j option

Why This Fails: For n = 4, the optimal break is 2 + 2 with product 4. However:

• When computing dp[4] with j = 2:
  • We need (4 - 2) * 2 = 2 * 2 = 4
  • But dp[2] * 2 = 1 * 2 = 2 (since breaking 2 gives 1+1 with product 1)
• Without the (num - j) * j option, we'd get the wrong answer

Solution: Always include both options in the max comparison:

dp[num] = max(dp[num], dp[num - j] * j, (num - j) * j)

Pitfall 2: Incorrect Loop Bounds

The Problem: Using incorrect loop bounds, especially making j go up to num instead of num - 1.

Incorrect Code:

for j in range(1, num + 1):  # Wrong: j shouldn't equal num
    dp[num] = max(dp[num], dp[num - j] * j, (num - j) * j)

Why This Fails: When j = num, we get num - j = 0, which means:

• We're not actually breaking the number (violating the "at least 2 parts" requirement)
• Accessing dp[0] which represents breaking 0, which is meaningless
• The product would be 0 * num = 0

Solution: Ensure j ranges from 1 to num - 1:

for j in range(1, num):  # Correct: j goes from 1 to num-1

Pitfall 3: Wrong Initialization Value

The Problem: Initializing the dp array with 0 instead of 1, or not initializing at all.

Incorrect Code:

dp = [0] * (n + 1)  # Wrong initialization

Why This Fails:

• With 0 initialization, all calculations involving dp[num - j] * j would result in 0
• The algorithm would never update from 0, leading to incorrect results
• For small numbers like n = 2, the answer should be 1 (1 + 1), not 0

Solution: Initialize with 1, which represents the minimum valid product:

dp = [1] * (n + 1)  # Correct initialization

Pitfall 4: Mathematical Optimization Trap

The Problem: Trying to optimize by only considering splits near the middle (e.g., j from num//2 to num-1), thinking symmetric splits are always optimal.

Incorrect Code:

for j in range(num // 2, num):  # Wrong: missing smaller j values
    dp[num] = max(dp[num], dp[num - j] * j, (num - j) * j)

Why This Fails: For larger numbers, the optimal solution often involves breaking into multiple 3's (and possibly a 2 or 4). For example:

• n = 10: Optimal is 3 + 3 + 4 = 3 * 3 * 4 = 36
• But if we only check splits near the middle, we might miss the pattern of using multiple 3's

Solution: Always check all possible splits from 1 to num-1 to ensure correctness:

for j in range(1, num):  # Check all possible splits