NUHMAN.com

🧩 Problem Statement

Given an integer n, break it into the sum of at least two positive integers, and maximize the product of those integers.

Return the maximum product you can get.

🔢 Example

python

Input: n = 10  
Output: 36  
Explanation: 10 = 3 + 3 + 4, and 3 × 3 × 4 = 36

✅ Constraints

• 2 ≤ n ≤ 58

💡 Key Insight

We need to find the best way to break n into integers such that their product is maximum. This is a classic integer partitioning problem with a twist—maximize the product, not the sum.

There are two main strategies:

1. Dynamic Programming
2. Mathematical Optimization (Greedy)

🔁 Solution 1: Dynamic Programming

Let’s build up the solution bottom-up using a DP array.

🧠 Idea:

• Let dp[i] be the maximum product for breaking integer i.
• Try all splits j from 1 to i - 1, and compare:
• j * (i - j) (no further breaking)
• j * dp[i - j] (break i - j further)
• Take the max of both.

✅ Python Code – DP Approach

python

class Solution:
    def integerBreak(self, n: int) -> int:
        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]

🔍 Step-by-Step Example for n = 10

• dp[2] = max(1×1) = 1
• dp[3] = max(1×2, 2×1) = 2
• dp[4] = max(1×3, 2×2, 3×1, 2×dp[2]) = 4
• ...
• dp[10] = 36

Final result: dp[10] = 36

🔢 Solution 2: Math-Based Greedy Approach

💡 Key Math Observations:

• Breaking numbers into 3s gives the best product.
• Prefer 3 over 2 because:
• 3 × 3 = 9 > 2 × 2 × 2 = 8

🎯 Strategy:

• If n == 2 → return 1
• If n == 3 → return 2
• While n > 4, keep subtracting 3 and multiply result
• Multiply the remainder

✅ Python Code – Math (Greedy) Approach

python

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2: return 1
        if n == 3: return 2
        
        product = 1
        while n > 4:
            product *= 3
            n -= 3
        
        return product * n

⏱️ Time & Space Complexity

ApproachTime ComplexitySpace ComplexityDPO(n²)O(n)Math/GreedyO(n)O(1)

📦 Test Cases

InputOutputExplanation211+1 = 2 → 1×1 = 1562+3 = 5 → 2×3 = 68183+3+2 → 3×3×2 = 1810363+3+4 → 3×3×4 = 36

✅ Conclusion

LeetCode 343: Integer Break beautifully combines DP intuition and greedy math strategies. While DP helps understand the structure of the solution, the math approach offers blazing fast performance with deeper number theory insight.

This is a must-practice problem for interviews involving integer partitioning, greedy choice, or optimization under constraints.