# 343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

# Solution

Approach 1: DP in O(N^2) time.

Approach 2: math in O(1) time: should split whenever there's a number >= 4 -- between 2 and 3, use as many 3s as possible since 3 * 3 > 2 * 2 * 2 for 6.

# Code (Python)

Approach 1:

    def integerBreak(self, n: int) -> int:
        # DP: table[i] -- integerBreak(i), initialized with table[1] = table[2] = 1
        # O(N^2) time
        table = [1 for _ in range(n + 1)]
        for num in range(3, n + 1):
            for component in range(1, num // 2 + 1):
                table[num] = max(
                    table[num],
                    table[component] * table[num-component],
                    component * table[num-component],
                    table[component] * (num - component),
                    component * (num - component)
                )
        return table[-1]

Approach 2:

    def integerBreak(self, n: int) -> int:
        # O(1) math solution: find the critical point where a split is better than a non-split
        # x/2 * x/2 >= x => x >= 4 when x is even
        # (x-1) / 2 * (x+1) / 2 >= x => x >= 5 when x is odd
        # basically it means any number >= 4 should be split into 2 parts with either 2 or 3
        # 3 is better than 2 because 3 * 3 > 2 * 2 * 2 (for a sum of 6), so use as many 3s as possible
        if n == 2:
            return 1
        if n == 3:
            return 2
        num_of_threes = n // 3
        remainder = n % 3
        if remainder == 0:
            return 3 ** num_of_threes
        elif remainder == 1:
            return 3 ** (num_of_threes - 1) * 2 * 2
        else:
            return 3 ** num_of_threes * 2

# Code (C++)

Approach 1:

Approach 2: