Problem
Given an integer n
, break it into the sum of k
positive integers, where k >= 2
, and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Constraints:
2 <= n <= 58
Solution
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
if (n < 4) return n - 1;
var res = 1;
while (n) {
if (n > 4) {
res *= 3;
n -= 3;
} else if (n <= 4 && n >= 2) {
res *= n;
n = 0;
} else if (n === 1) {
n = 0;
}
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).