Integer Break

medium math dp

Problem

Given an integer n ≥ 2, break it into at least two positive integers whose product is maximized. Return that maximum product.

Inputn = 10

Output36

10 = 3 + 3 + 4 → 3·3·4 = 36.

n (2..15)

def integer_break(n):
    dp = [0] * (n + 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]

function integerBreak(n) {
  const dp = new Array(n + 1).fill(0);
  for (let i = 2; i <= n; i++) {
    for (let j = 1; j < i; j++) {
      dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
    }
  }
  return dp[n];
}

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

int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            dp[i] = max({dp[i], j * (i - j), j * dp[i - j]});
    return dp[n];
}

Explanation

We split n into at least two positive pieces and want their product to be as large as possible. We build the answer bottom-up: dp[i] is the best product you can get by breaking i into two or more pieces.

To fill dp[i], we try every first cut j from 1 to i-1. For each cut there are two options: j * (i - j) leaves the rest as a single whole piece, while j * dp[i - j] breaks the rest further. We take the max over both options and over all j.

The reason we need both options is that sometimes leaving a chunk whole is better (for small numbers) and sometimes splitting it further wins (for larger ones). Letting the DP compare them handles every case.

Example: n = 10. The DP discovers 10 = 3 + 3 + 4 giving 3 * 3 * 4 = 36, which beats any other split. So dp[10] = 36.

Two nested loops up to n make this O(n²) time with O(n) space.

Time: O(n²) Space: O(n)