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.
// 4ms, 52%
class Solution {
public:
int integerBreak(int n) {
vector<int> dp (n + 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i/2; j++) {
dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i-j]));
}
}
return dp[n];
}
};
// 4ms, 52%
class Solution {
vector<int> dp;
int check(int n) {
if (dp[n] > 0) return dp[n];
int r = 0;
for (int i = 1; i <= n/2; i++) {
int a = check(i) * check(n - i);
if (a > r) {
r = a;
}
}
return dp[n] = r;
}
public:
int integerBreak(int n) {
if (n == 2)
return 1;
if (n == 3)
return 2;
dp.resize(n + 1, -1);
dp[1] = 1;
dp[2] = 2;
if (n > 2) dp[3] = 3;
return check(n);
}
};