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.

Sitelet https://gitgood.dev/coding/integer-break

gitGood.dev

← 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 7 test cases (5 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.

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.