Problem statement

https://leetcode.com/problems/integer-break/

Solution

We can do it with dp way, where dp[i] is the answer for number i. Then to evaluate it, we need to check for every 1 <= j < i: j *(i-j) and j * dp[i-j]. Complexity will be O(n^2) if we make assumption that multiplication is done in O(1).

We can note that actually all factors should be 2 or 3, for example if we have 4, we split it into 2, 2, if it is 5, we split into 2, 3 and so on.

Complexity

In this way time and space complexity is O(n)

Code

class Solution:
    def integerBreak(self, n):
        def dp(n):
            return n if n < 5 else dp(n-3)*3
        
        if n <= 3: return n - 1
        if n == 4: return n
        return dp(n)

Remark

See similar 1808. Maximize Number of Nice Divisors problem.