LeetCode Daily Log — Integer Break

https://leetcode.cn/problems/integer-break/

Date: 2025-11-28
Difficulty: Medium
Topics: Dynamic Programming, Math
Status: Solved

---

1. Problem Summary

Given an integer n, split it into at least two positive integers such that the product of these integers is maximized. Return the maximum possible product.

---

2. My Observations

While checking numbers 7–10 manually, I found this pattern:

• 7 → 2 + 2 + 3 = 12

• 8 → 3 + 3 + 2 = 18

• 9 → 3 + 3 + 3 = 27

• 10 → 3 + 3 + 4 = 36

The pattern shows:

1. The split numbers mostly increase one by one as n increases

2. The number 3 appears very frequently

3. The product grows fastest when more 3’s are used

This motivated the question: why is “3” always optimal?

---

3. Dynamic Programming Solution

Define:

dp[i] = the maximum product for integer i after splitting into at least two parts

For each i:

• Split i into j and i - j

• Two possibilities:

  • Do not split i - j further: j * (i - j)

  • Continue splitting i - j: j * dp[i - j]

State transition:

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

Java code:

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;

        int[] dp = new int[n+1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i],
                        Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

---

4. Mathematical Insight — Why 3 Is Optimal

There is a known mathematical fact:

To maximize the product of numbers with a fixed sum, the most optimal real number to split into is e (approximately 2.718).

We prove this briefly:

1. Suppose the number n is split into k identical real numbers x
   Then:
   k * x = n → k = n / x

2. The product is:
   P = x^(n/x)

3. To maximize, take the derivative of ln(P):
   ln(P) = (n ln x) / x
   Derivative = 0 → 1 - ln x = 0 → x = e

Since integer decomposition is required, we compare nearby integers:

• 2 → 2^(1/2) = 1.414

• 3 → 3^(1/3) = 1.442 (highest)

• 4 → 4^(1/4) = 1.414

• 5 → 5^(1/5) = 1.38

Therefore, 3 is the best integer for maximizing product.

Additional rules:

• Never split into 1, because multiplying by 1 reduces efficiency

• If remainder is 1, turn “3 + 1” into “2 + 2” (because 2 2 > 3 1)

This gives the following cases:

• If n % 3 == 0 → all 3’s

• If n % 3 == 1 → use one fewer 3, add two 2’s

• If n % 3 == 2 → use a 2 at the end

Mathematical solution in Java:

public int integerBreak(int n) {
    if (n == 2) return 1;
    if (n == 3) return 2;

    int q = n / 3;
    int r = n % 3;

    if (r == 0) return (int) Math.pow(3, q);
    if (r == 1) return (int) Math.pow(3, q - 1) * 4;
    return (int) Math.pow(3, q) * 2;
}

---

5. Key Takeaways

1. The dynamic programming approach works for all n and is intuitive.

2. The mathematical approach is constant time and elegant.

3. The number 3 provides the highest “unit productivity” for maximizing product.

4. Avoid 1 in the final split.

5. Integer break is a classic combination of DP and mathematical optimization.

---

6. Notes for Future Practice

• Revisit the AM-GM inequality when dealing with “maximize product with fixed sum” problems.

• Recognize integer break as a classical optimization problem.

• Remember the special case: convert 3 + 1 into 2 + 2.

• Use the math solution when n is large for higher efficiency.