Greedy Algorithm to Maximize the Split Product (Integer Break)

Given an integer n, find two or more integers such that their sum is equal to n, where the product of these integers is maximized, and return this product.

Constraints
n ≤ 100,000
Example 1
Input
n = 11
Output
54
Explanation
3 + 3 + 3 + 2 = 11 and 3 * 3 * 3 * 2 = 54

Maximize the Split Product (Integer Break) via Greedy Algorithm

Given number 6, we can split it into 3*3 which is the largest (other than 2*2*2, or 3*2*1, or 2*2*1*1). Therefore, we can greedily pick/split 3 until the number is smaller than 4 – then we multiply the remaining.

int maxSplitProduct(int n) {
    if ((n == 1) or (n == 2)) return 1;
    if (n == 3) return 2;
    int ans = 1;
    while (n > 4) {
        n -= 3;
        ans *= 3;
    }
    return ans * n;
}

This can also be solved via Dynamic Programming – Integer Break. The time complexity is O(N) which is superior than Dynamic Programming Algorithm in this case.

See also: Teaching Kids Programming – Maximum Product by Splitting Integer using Dynamic Programming or Greedy Algorithm

–EOF (The Ultimate Computing & Technology Blog) —