# 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.

Example 1:

``````Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
``````

Example 2:

``````Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
``````

Note: You may assume that  n  is not less than 2 and not larger than 58.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

``````class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 1);
for (int i = 3; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
};
``````

….

``````class Solution {
public:
int integerBreak(int n) {
if (n == 2 || n == 3) return n - 1;
int res = 1;
while (n > 4) {
res *= 3;
n -= 3;
}
return res * n;
}
};
``````

``````class Solution {
public:
int integerBreak(int n) {
vector<int> dp{0, 0, 1, 2, 4, 6, 9};
for (int i = 7; i <= n; ++i) {
dp.push_back(3 * dp[i - 3]);
}
return dp[n];
}
};
``````

``````class Solution {
public:
int integerBreak(int n) {
if (n == 2 || n == 3) return n - 1;
if (n == 4) return 4;
n -= 5;
return (int)pow(3, (n / 3 + 1)) * (n % 3 + 2);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/343

https://leetcode.com/problems/integer-break/

https://leetcode.com/problems/integer-break/discuss/80694/Java-DP-solution

https://leetcode.com/problems/integer-break/discuss/80785/O(log(n))-Time-solution-with-explanation

https://leetcode.com/problems/integer-break/discuss/80720/Easy-to-understand-C%2B%2B-with-explanation

https://leetcode.com/problems/integer-break/discuss/80689/A-simple-explanation-of-the-math-part-and-a-O(n)-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation