Let's start with simple cases, "->" means decompose:

2 -> 1 1 = 1

3 -> 1 2 = 2

4 -> 2 2 = 4

5 -> 2 3 = 6

6 -> 3 3 = 9

7 -> 3 2 2 = 12

8 -> 3 3 2 = 18

9 -> 3 3 3 = 27

10 -> 3 3 2 2 = 36

It's easy to know that 2 and 3 are greater than their decompositions. Every number except 2 and 3 should be decompose since this action will maximize result.

So the code is pretty simple. We maintain a list named "factor" to store factors in every steps, and then update the min item by one if it wouldn't exceed 4 (only 2 and 3 are allowed). For example, when we update 9 (factors: 3 3 3), the min item is 3, if I update it to 4, it would exceed our role. So we delete 3 and add two 2 to the list. So the result after update is (factors: 3 3 2 2)

'''

def integerBreak(self, n):

factor = [1,1]

for i in range(3,n+1):

# find the min item to update

update = factor.index(min(factor))

if factor[update]==3:

# cannot add anymore, replace it with [2,2]

del factor[update]

factor+=[2,2]

else:

factor[update]+=1

return reduce(lambda x,y:x*y,factor)

'''