Dynamic Programming • Math

Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Try Interactive Simulator

Overview

This problem asks us to find the optimal way to break down a number to maximize the product of its parts. It demonstrates overlapping subproblems perfectly.

The Logic

To break `i`, we can try all possible first parts `j` (from 1 to `i-1`). The second part is `i-j`.

To Break or Not?

For the second part `i-j`, we have a choice: we can leave it as is, or we can break it down further. That's why we compare `j * (i-j)` with `j * dp[i-j]`.

Math Optimization

Fun fact: breaking a number into 3s maximizes the product. A greedy math approach runs in O(1) time, but this DP solution runs in O(N^2).

i (Number)

-

j (Split 1)

-

i-j (Split 2)

-

DP Array (Max Product)

0

1

0

2

0

3

0

4

0

5

0

6

0

Code Tracker

:::

1let dp = new Array(n + 1).fill(0);

2dp[1] = 1;

3for (let i = 2; i <= n; i++) {

4 for (let j = 1; j < i; j++) {

5 let p1 = j * (i - j);

6 let p2 = j * dp[i - j];

7 dp[i] = Math.max(dp[i], p1, p2);

8 }

9}

10return dp[n];