(LeetCode) — same core problem (break integer into sum of at least two positive integers to maximize product).

Source: tutorialhorizon article preserved in source_links.

Solution

We present three methods: naive recursion (exponential), dynamic programming (bottom-up O(n^2)), and a mathematical/greedy approach using factor 3 which yields an O(1) / O(n) solution.

Method 1 — Recursive brute force

Intuition

For each possible first cut i (1..n-1) either take the product i * (n-i) (stop cutting the second piece) or further cut the remaining piece and take i * MPC(n-i). The best among all i is the answer. This explores all partitions and is exponential.

Approach

Base cases: MPC(0)=0, MPC(1)=0 (because at least one cut is required and single unit cannot be split to increase product).
For k from 1 to n-1 compute max(i*(n-i), i*MPC(n-i)) and take the maximum.
Return the maximum over all

Related Tags

Continue Practicing