15.4 Maximum product cutting problem¶
Question
Given a positive integer \(n\), split it into a sum of at least two positive integers. What is the largest possible product of those integers? The problem is illustrated in Figure 15-13.
Figure 15-13 Definition of the maximum product cutting problem
Description of Figure 15-13: Problem definition for maximum product cutting
For a fixed sum, choose how many parts to cut and their sizes to maximize their product.
Given an integer n ≥ 2, split n into a sum of m ≥ 2 positive integers n = n₁ + n₂ + … + nₘ (with subscripts 1 through m) so as to maximize the product n₁ × n₂ × … × nₘ.
A symbolic bar diagram shows a solid gray bar of total length n above and an equal-length segmented colored bar below cut by vertical dashed lines into n₁, n₂, n₃, …, nₘ₋₂, nₘ₋₁, nₘ (ending at subscripts m minus 2, m minus 1, and m) from left to right, with dashed alignment lines at both ends showing the parts sum to n; below reads "Given integer n, find max(n₁ × n₂ × n₃ × … × nₘ₋₂ × nₘ₋₁ × nₘ)".
The subscripted labels and ellipsis represent an arbitrary m-part split rather than requiring at least six parts; m can be as small as 2. Neither n, m, nor concrete part sizes are fixed here, so schematic bar widths do not represent numeric values.
Suppose we split \(n\) into \(m\) integers that will be factors in the product. Denote the \(i\)-th factor by \(n_i\), so that
Our goal is to maximize the product of all these integer factors:
We need to determine how many parts \(m\) to create and what each \(n_i\) should be.
1. Choosing a greedy strategy¶
The product of two integers is often greater than their sum. Suppose we split off a factor of \(2\) from \(n\), giving the product \(2(n-2)\). Comparing this product with \(n\) gives:
As shown in Figure 15-14, when \(n \geq 4\), splitting off a \(2\) increases the product. This suggests that every integer greater than or equal to \(4\) should be split further.
Greedy strategy 1: If a factor \(\geq 4\) appears in a split, divide it further. The final split should contain only the factors \(1\), \(2\), and \(3\).
Figure 15-14 Splitting increases the product
Description of Figure 15-14: Splitting a large factor does not decrease the product
Larger integer factors can be split further without decreasing the product.
In maximum product cutting, test whether an integer factor n should be split further by comparing n against the product of 2 and n - 2.
Above sits a gray bar of length n; below sits an equal-length bar split at a vertical dashed line into a short green "2" on the left and a blue "n - 2" on the right, captioned below "When n ≥ 4, 2(n - 2) ≥ n always holds. Thus the final partition should contain only factors 1, 2, 3".
Because 2(n - 2) - n = n - 4, the product stays equal at n = 4 and strictly increases for n > 4. Repeatedly splitting factors of 4 or greater never decreases the product. Thus at least one optimal split uses only 1, 2, and 3. An optimal split may also retain a 4.
Next, consider which factor is best. Of \(1\), \(2\), and \(3\), clearly \(1\) is the worst: \(1 \times (n-1) < n\) always holds, so splitting off a \(1\) reduces the product.
As shown in Figure 15-15, when \(n = 6\), we have \(3 \times 3 > 2 \times 2 \times 2\). This means that splitting into factors of \(3\) is better than splitting into factors of \(2\).
Greedy strategy 2: A split should contain at most two factors of \(2\), because three \(2\)s can always be replaced with two \(3\)s to obtain a larger product.
Figure 15-15 Optimal factors
Description of Figure 15-15: Replacing three 2s with two 3s
Compare two local splits with the same sum of 6: three 2s versus two 3s.
Building on the result that an optimal split need only consider the factors 1, 2, and 3, this figure examines a split that already contains three 2s while keeping all remaining factors unchanged.
At the top is a solid gray bar of total length n. On the middle row, three consecutive blue blocks labeled "2" (total length 6) appear on the left, followed by a gray remainder segment on the right. On the bottom row, only the left span of equal length 6 is drawn, replaced by two purple blocks labeled "3"; the gray remainder on the right is drawn only on the middle row and does not take part in the replacement. A downward solid gray arrow in the center marks the conversion from three 2s to two 3s, and a caption below reads "Whenever there are three 2s, greedily replace them with two 3s".
The product of three 2s is 8 and the product of two 3s is 9, while both sum to 6. Let P be the product of the remaining positive integer factors, taking P = 1 when there are none. This local replacement increases the overall product from 8P to 9P, so an optimal split retains at most two 2s. This algebraic argument provides the derivation for the local replacement shown in the figure.
These observations lead to the following greedy strategy.
- Starting with \(n\), keep splitting off factors of \(3\) until the remainder is \(0\), \(1\), or \(2\).
- If the remainder is \(0\), then \(n\) is a multiple of \(3\), and no further action is needed.
- If the remainder is \(2\), keep it without splitting it further.
- If the remainder is \(1\), replace the last \(3\) and the remaining \(1\) with two \(2\)s, since \(2 \times 2 > 1 \times 3\).
2. Code implementation¶
As shown in Figure 15-16, we do not need a loop to split the integer. Floor division gives the number of \(3\)s, denoted by \(a\), and the modulo operation gives the remainder \(b\). Thus:
For the boundary cases \(n \leq 3\), we must split off a \(1\), giving a product of \(1 \times (n - 1)\).
def max_product_cutting(n: int) -> int:
"""Maximum product after splitting: greedy algorithm"""
# When n <= 3, one part must be 1
if n <= 3:
return 1 * (n - 1)
# Greedily split off parts of size 3; a is the number of 3s and b is the remainder
a, b = n // 3, n % 3
if b == 1:
# When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return int(math.pow(3, a - 1)) * 2 * 2
if b == 2:
# When the remainder is 2, no adjustment is needed
return int(math.pow(3, a)) * 2
# When the remainder is 0, no adjustment is needed
return int(math.pow(3, a))
/* Maximum product after splitting: greedy algorithm */
int maxProductCutting(int n) {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
int a = n / 3;
int b = n % 3;
if (b == 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return (int)pow(3, a - 1) * 2 * 2;
}
if (b == 2) {
// When the remainder is 2, no adjustment is needed
return (int)pow(3, a) * 2;
}
// When the remainder is 0, no adjustment is needed
return (int)pow(3, a);
}
/* Maximum product after splitting: greedy algorithm */
int maxProductCutting(int n) {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
int a = n / 3;
int b = n % 3;
if (b == 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return (int) Math.pow(3, a - 1) * 2 * 2;
}
if (b == 2) {
// When the remainder is 2, no adjustment is needed
return (int) Math.pow(3, a) * 2;
}
// When the remainder is 0, no adjustment is needed
return (int) Math.pow(3, a);
}
/* Maximum product after splitting: greedy algorithm */
int MaxProductCutting(int n) {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
int a = n / 3;
int b = n % 3;
if (b == 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return (int)Math.Pow(3, a - 1) * 2 * 2;
}
if (b == 2) {
// When the remainder is 2, no adjustment is needed
return (int)Math.Pow(3, a) * 2;
}
// When the remainder is 0, no adjustment is needed
return (int)Math.Pow(3, a);
}
/* Maximum product after splitting: greedy algorithm */
func maxProductCutting(n int) int {
// When n <= 3, one part must be 1
if n <= 3 {
return 1 * (n - 1)
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
a := n / 3
b := n % 3
if b == 1 {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return int(math.Pow(3, float64(a-1))) * 2 * 2
}
if b == 2 {
// When the remainder is 2, no adjustment is needed
return int(math.Pow(3, float64(a))) * 2
}
// When the remainder is 0, no adjustment is needed
return int(math.Pow(3, float64(a)))
}
/* Maximum product after splitting: greedy algorithm */
func maxProductCutting(n: Int) -> Int {
// When n <= 3, one part must be 1
if n <= 3 {
return 1 * (n - 1)
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
let a = n / 3
let b = n % 3
if b == 1 {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return pow(3, a - 1) * 2 * 2
}
if b == 2 {
// When the remainder is 2, no adjustment is needed
return pow(3, a) * 2
}
// When the remainder is 0, no adjustment is needed
return pow(3, a)
}
/* Maximum product after splitting: greedy algorithm */
function maxProductCutting(n) {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
let a = Math.floor(n / 3);
let b = n % 3;
if (b === 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return Math.pow(3, a - 1) * 2 * 2;
}
if (b === 2) {
// When the remainder is 2, no adjustment is needed
return Math.pow(3, a) * 2;
}
// When the remainder is 0, no adjustment is needed
return Math.pow(3, a);
}
/* Maximum product after splitting: greedy algorithm */
function maxProductCutting(n: number): number {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
let a: number = Math.floor(n / 3);
let b: number = n % 3;
if (b === 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return Math.pow(3, a - 1) * 2 * 2;
}
if (b === 2) {
// When the remainder is 2, no adjustment is needed
return Math.pow(3, a) * 2;
}
// When the remainder is 0, no adjustment is needed
return Math.pow(3, a);
}
/* Maximum product after splitting: greedy algorithm */
int maxProductCutting(int n) {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
int a = n ~/ 3;
int b = n % 3;
if (b == 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return (pow(3, a - 1) * 2 * 2).toInt();
}
if (b == 2) {
// When the remainder is 2, no adjustment is needed
return (pow(3, a) * 2).toInt();
}
// When the remainder is 0, no adjustment is needed
return pow(3, a).toInt();
}
/* Maximum product after splitting: greedy algorithm */
fn max_product_cutting(n: i32) -> i32 {
// When n <= 3, one part must be 1
if n <= 3 {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
let a = n / 3;
let b = n % 3;
if b == 1 {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
3_i32.pow(a as u32 - 1) * 2 * 2
} else if b == 2 {
// When the remainder is 2, no adjustment is needed
3_i32.pow(a as u32) * 2
} else {
// When the remainder is 0, no adjustment is needed
3_i32.pow(a as u32)
}
}
/* Maximum product after splitting: greedy algorithm */
int maxProductCutting(int n) {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1);
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
int a = n / 3;
int b = n % 3;
if (b == 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return pow(3, a - 1) * 2 * 2;
}
if (b == 2) {
// When the remainder is 2, no adjustment is needed
return pow(3, a) * 2;
}
// When the remainder is 0, no adjustment is needed
return pow(3, a);
}
/* Maximum product after splitting: greedy algorithm */
fun maxProductCutting(n: Int): Int {
// When n <= 3, one part must be 1
if (n <= 3) {
return 1 * (n - 1)
}
// Greedily split off parts of size 3; a is the number of 3s and b is the remainder
val a = n / 3
val b = n % 3
if (b == 1) {
// When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return 3.0.pow((a - 1)).toInt() * 2 * 2
}
if (b == 2) {
// When the remainder is 2, no adjustment is needed
return 3.0.pow(a).toInt() * 2 * 2
}
// When the remainder is 0, no adjustment is needed
return 3.0.pow(a).toInt()
}
### Maximum product after splitting: greedy algorithm ###
def max_product_cutting(n)
# When n <= 3, one part must be 1
return 1 * (n - 1) if n <= 3
# Greedily split off parts of size 3; a is the number of 3s and b is the remainder
a, b = n / 3, n % 3
# When the remainder is 1, replace one pair 1 * 3 with 2 * 2
return (3.pow(a - 1) * 2 * 2).to_i if b == 1
# When the remainder is 2, no adjustment is needed
return (3.pow(a) * 2).to_i if b == 2
# When the remainder is 0, no adjustment is needed
3.pow(a).to_i
end
Visualize execution
Figure 15-16 Calculating the maximum product
Description of Figure 15-16: Direct calculation for maximum product cutting
Use integer division and remainder to write n = 3 × a + b and adjust the split by remainder case, handling small cases n = 2 and n = 3 separately so at least two parts are formed.
Given an integer n ≥ 2, split n into at least two positive integers summing to n to maximize their product.
Because the optimal greedy strategy extracts as many 3s as possible, the code avoids cutting in a loop and instead computes quotient a = n // 3 and remainder b = n % 3 in one step to get the count a of 3s and remainder b.
The diagram decomposes a bar of length n into "a copies of 3" and a "Remainder b" segment above the identity n = 3 × a + b (with a = n // 3 and b = n % 3 in {0, 1, 2}). Drawing "Remainder b" on the left is purely symbolic—neither fixing concrete values of n or b nor implying left-to-right cutting—while ellipses between blue 3-blocks stand for additional copies of 3.
The table below supplies all five cases from the chapter text and code (not drawn separately in the figure). Boundary inputs n = 2 and n = 3 must be cut into at least two parts rather than left uncut as n.
When n ≥ 4 and b = 1, we have a ≥ 1, so at least one 3 can be recombined with remainder 1 into 2 + 2—keeping sum 4 while raising their local product from 3 to 4—leaving a - 1 copies of 3 and product 3^(a - 1) × 2 × 2 (3 raised to the exponent (a minus 1), times 2 times 2).
| Condition | Split or recombination | Maximum product |
|---|---|---|
| n=2 | 1+1 | 1 |
| n=3 | 1+2 | 2 |
| n ≥ 4, b = 0 | a copies of 3 | 3^a |
| n ≥ 4, b = 1 | a - 1 copies of 3 and two 2s; replace one 3 plus remainder 1 with 2 + 2 | 3^(a−1)×2×2 |
| n ≥ 4, b = 2 | a copies of 3 and one 2 | 3^a×2 |
In the figure, "Remainder b" represents the quotient-remainder decomposition: b = 0 leaves no remainder piece, b = 2 keeps 2 as a factor, and b = 1 recombines with one 3 as in the table—0 is never used as a factor.
The time complexity depends on how the programming language implements exponentiation. Python, for example, offers three common ways to compute powers.
- The
**operator and thepow()function both have a time complexity of \(O(\log a)\). - The
math.pow()function calls the C library'spow()function internally, performing floating-point exponentiation in \(O(1)\) time.
The variables \(a\) and \(b\) use constant extra space, so the space complexity is \(O(1)\).
3. Proof of correctness¶
We use proof by contradiction, considering only \(n \geq 4\).
- All factors are \(\leq 3\): Suppose an optimal split contains a factor \(x\) that is \(\geq 4\). We can split it further to obtain \(2(x-2)\), giving a greater (or equal) product. This contradicts the assumption.
- The split contains no \(1\): Suppose an optimal split contains a factor of \(1\). We can merge it into another factor to obtain a larger product, contradicting the assumption.
- The split contains at most two \(2\)s: Suppose an optimal split contains three \(2\)s. Replacing them with two \(3\)s gives a larger product, contradicting the assumption.