LeetCode 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.
'''
'''
first a few integers:
1: 0 (not available)
2: 1*1=1
3: 1*2=2
4: 2*2=4
5: 2*3=6
6: 3*3=9
7: 3*4=12

for n >= 4, can be break into 2s and 3s to max the product
proof:
if break into multiple numbers and one of it >= 5: it can be broken to get a larger product
so the max single number is 4, which is also 2*2   
   
'''

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 0
        elif n == 2: return 1
        elif n == 3: return 2
        elif n == 4: return 4
        else:
            result = 1
            while n > 4:
                result *= 3
                n -=3
            result *= n
            return result