#break into as much 3 as possible, then either 4 or 2
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if (n==2)or(n==3):
return n-1
mod=n%3
if mod==1:
return pow(3,(n-4)/3)*4
elif mod==2:
return pow(3,n/3)*2
else:
return pow(3,n/3)
#dynamic programming solution
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
# integerBreak(n) = max(integerBreak(n - 2) * 2, integerBreak(n - 3) * 3)
if n<4 :
return n-1
res = [0, 1, 2,3]
for i in xrange(4, n + 1):
res[i % 4] = max(res[(i - 2) % 4] * 2, res[(i - 3) % 4] * 3)
return res[n % 4]
