Integer Break

Integer Break: the approach in brief

The problem

Given the integer n, split it into the sum of at least two positive integers. The parts may be equal, and their order does not affect the result. The product of a split is the multiplication of all its parts.

Pattern

Integer Break is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Fibonacci Style) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Approach outline

1. Consider defining the best product obtainable for every smaller integer up to `n`.
2. For a fixed total, try choosing one part and deciding whether the remainder stays whole or is split further.
3. The answer for a total can be formed from products involving every first part from 1 through one less than that total.

Complexity

The reference solution runs in O(n^2) time and O(n) space.