Integer Break Python Solution with Tests

Tested Python solution for LeetCode 343 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 343, Medium. Topics: Math, Dynamic Programming. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 343   # by problem number
lcpy gen -s integer_break   # by problem name

​

Problem

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

​

Examples

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 * 1 = 1.

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

​

Constraints

• 2 <= n <= 58

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n^2)
    # Space: O(n)
    def integer_break(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[1] = 1

        for target in range(2, n + 1):
            for part in range(1, target):
                dp[target] = max(dp[target], part * (target - part), part * dp[target - part])

        return dp[n]

​

Complexity

Time	Space
O(n^2)	O(n)

​

Tags

NeetCode 250, NeetCode All.