343 - Integer Break
Written on October 29, 2017
Tweet
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.
- no cut on the left part, optimal cut on the right part;
- optimal cut on the left part, no cut on the right part;
- optimal cut on the left part, optimal cut on the right part;
- no cut on the left part, no cut on the right part;
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
dp = [1] * (n + 1)
for i in xrange(2, n + 1):
for j in xrange(1, i):
dp[i] = max(dp[i], max(dp[j], j) * max(dp[i - j], i - j))
return dp[-1]