# 9 line elegant Python solution with explanation from engineer perspective

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)
'''

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.