How do you approach Integer Break?

For each i, try a first part j and either stop (j(i-j)) or break the rest (jdp[i-j]).

What are common mistakes on Integer Break?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Integer Break

MediumAlgorithms

Description

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.

Example 1

Input: n = 2

Output: 1

Explanation: 2 = 1 + 1, product 1.

Example 2

Input: n = 10

Output: 36

Explanation: 10 = 3 + 3 + 4, product 36.

Constraints

- 2 <= n <= 58

Integer Break: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 4 test cases (2 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 2-step hint ladder

For each i, try a first part j and either stop (j*(i-j)) or break the rest (j*dp[i-j]).
dp[1] = 1 seeds the recurrence.

The optimal approach

Show the approach: The approach

Partition DP. `dp[i]` is the max product from breaking `i` (into 2+ parts). For each split `j`, the rest can stay whole (`j·(i-j)`) or be broken further (`j·dp[i-j]`); take the max over all `j`.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.