Maximum Product Cutting

Problem

Given a rope of length n (integer), cut it into at least two integer-length pieces so that the product of the piece lengths is maximized. Return the maximum product.

Notes and constraints:

• At least one cut must be made (so for n <= 1 the problem is degenerate).
• Practical input: n is a positive integer; typical interview constraints use n up to a few thousands.

Examples

Example 1

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1 -> 1 * 1 = 1

Example 2

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4 -> 3 * 3 * 4 = 36

Related problems: [[Integer Break]] (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

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

Edge cases: small n (2 or 3) should be handled explicitly to ensure at least one cut.

Recursion tree

The solution is simple, but we see recursive subproblems.

graph TD;
	A("MPC(4)") --- B("MPC(3)") & C("MPC(2)"):::blue & D("MPC(1)"):::orange
	B --- E("MPC(2)"):::blue & F("MPC(1)"):::orange
	C --- G("MPC(1)"):::orange
	
	
	classDef blue fill:#ADD8E6,stroke:#000,stroke-width:1px;
	classDef orange fill:#FFA07A,stroke:#333,stroke-width:2px;

Code

C++

class Solution {
 public:
  int maxProductCutting(int n) {
    if (n == 0 || n == 1) return 0;
    int ans = 0;
    for (int i = 1; i < n; ++i) {
      ans = max(ans, max(i * (n - i), i * maxProductCutting(n - i)));
    }
    return ans;
  }
};

Go

package main

func maxProductCutting(n int) int {
    if n == 0 || n == 1 { return 0 }
    ans := 0
    for i := 1; i < n; i++ {
    ans = max(ans, max(i*(n-i), i*maxProductCutting(n-i)))
    }
    return ans
}

func max(a, b int) int { if a > b { return a }; return b }

Java

class Solution {
  public int maxProductCutting(int n) {
    if (n == 0 || n == 1) return 0;
    int ans = 0;
    for (int i = 1; i < n; ++i) {
      ans = Math.max(ans, Math.max(i * (n - i), i * maxProductCutting(n - i)));
    }
    return ans;
  }
}

Python

from typing import Optional

class Solution:
  def maxProductCutting(self, n: int) -> int:
    if n == 0 or n == 1:
      return 0
    ans = 0
    for i in range(1, n):
      ans = max(ans, max(i * (n - i), i * self.maxProductCutting(n - i)))
    return ans

Complexity

• ⏰ Time complexity: O(2^n) (exponential) — explores many overlapping partitions.
• 🧺 Space complexity: O(n) recursion stack.

Method 2 — Dynamic programming (bottom-up)

Intuition

Subproblems overlap; store dp[k] = maximum product obtainable for length k (with at least one cut inside the k segment). Build dp from smaller lengths to larger ones: for each k consider first cut i and combine i with either k-i (no further cut) or dp[k-i] (further cuts).

Approach

1. Initialize dp[0]=0, dp[1]=0.
2. For len from 2 to n:
   • Set dp[len] = 0.
   • For i in 1..len-1 compute dp[len] = max(dp[len], max(i*(len-i), i*dp[len-i])).
3. Return dp[n].

This runs in O(n^2) time and O(n) space.

Code

C++

class Solution {
 public:
  int maxProductCutting(int n) {
    if (n <= 1) return 0;
    vector<int> dp(n + 1, 0);
    dp[0] = 0; dp[1] = 0;
    for (int len = 2; len <= n; ++len) {
      int best = 0;
      for (int i = 1; i < len; ++i) {
        best = max(best, max(i * (len - i), i * dp[len - i]));
      }
      dp[len] = best;
    }
    return dp[n];
  }
};

Go

package main

func maxProductCutting(n int) int {
    if n <= 1 { return 0 }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 0
    for length := 2; length <= n; length++ {
        best := 0
        for i := 1; i < length; i++ {
            best = max(best, max(i*(length-i), i*dp[length-i]))
        }
        dp[length] = best
    }
    return dp[n]
}

func max(a, b int) int { if a > b { return a }; return b }

Java

class Solution {
  public int maxProductCutting(int n) {
    if (n <= 1) return 0;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 0;
    for (int len = 2; len <= n; ++len) {
      int best = 0;
      for (int i = 1; i < len; ++i) {
        best = Math.max(best, Math.max(i * (len - i), i * dp[len - i]));
      }
      dp[len] = best;
    }
    return dp[n];
  }
}

Python

from typing import List

class Solution:
  def maxProductCutting(self, n: int) -> int:
        if n <= 1:
            return 0
        dp: List[int] = [0] * (n + 1)
        dp[0], dp[1] = 0, 0
        for length in range(2, n + 1):
            best = 0
            for i in range(1, length):
                best = max(best, max(i * (length - i), i * dp[length - i]))
            dp[length] = best
        return dp[n]

Complexity

• ⏰ Time complexity: O(n^2) — double loop over lengths and split positions.
• 🧺 Space complexity: O(n) for the dp array.

Method 3 — Greedy / Mathematical (use 3s)

Intuition

For large n the maximum product is achieved by breaking the integer into as many 3s as possible, with special handling when remainder is 1 (turn a 3+1 into 2+2). This yields an O(1)/O(n) solution depending on implementation.

Approach

1. If n == 2 return 1. If n == 3 return 2 (since at least one cut required).
2. Let count3 = n / 3 and rem = n % 3.
3. If rem == 0 return 3^count3.
4. If rem == 1 return 3^(count3-1) * 4 (use one fewer 3 and two 2s).
5. If rem == 2 return 3^count3 * 2.

This uses exponentiation and runs quickly for moderate n (watch overflow for large n).

Code

C++

class Solution {
 public:
  long long maxProductCutting(int n) {
    if (n == 2) return 1;
    if (n == 3) return 2;
    long long cnt3 = n / 3;
    int rem = n % 3;
    if (rem == 1) {
      cnt3 -= 1;
      long long res = 1;
      while (cnt3--) res *= 3;
      return res * 4;
    } else if (rem == 2) {
      long long res = 1;
      while (cnt3--) res *= 3;
      return res * 2;
    } else {
      long long res = 1;
      while (cnt3--) res *= 3;
      return res;
    }
  }
};

Go

package main

func maxProductCutting(n int) int {
    if n == 2 { return 1 }
    if n == 3 { return 2 }
    cnt3 := n / 3
    rem := n % 3
    if rem == 1 {
        cnt3 -= 1
        res := 1
        for cnt3 > 0 { res *= 3; cnt3-- }
        return res * 4
    }
    res := 1
    for cnt3 > 0 { res *= 3; cnt3-- }
    if rem == 2 { return res * 2 }
    return res
}

Java

class Solution {
  public long maxProductCutting(int n) {
    if (n == 2) return 1;
    if (n == 3) return 2;
    int cnt3 = n / 3;
    int rem = n % 3;
    if (rem == 1) {
      cnt3 -= 1;
      long res = 1;
      while (cnt3-- > 0) res *= 3;
      return res * 4;
    }
    long res = 1;
    while (cnt3-- > 0) res *= 3;
    if (rem == 2) return res * 2;
    return res;
  }
}

Python

class Solution:
  def maxProductCutting(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2
        cnt3 = n // 3
        rem = n % 3
        if rem == 1:
            cnt3 -= 1
            res = 1
            for _ in range(cnt3):
                res *= 3
            return res * 4
        res = 1
        for _ in range(cnt3):
            res *= 3
        if rem == 2:
            return res * 2
        return res

Complexity

• ⏰ Time complexity: O(1) for greedy arithmetic (or O(log n) if using fast exponentiation) ; O(n^2) for DP ; exponential for recursion.
• 🧺 Space complexity: O(1) for greedy, O(n) for DP and recursion stack.