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: 2Output: 1Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10Output: 36Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max(dp[j] * (i - j), j * (i - j)));
}
// System.out.println(String.format("dp[%d]: %d", i, dp[i]));
}
return dp[n];
}
}
这题好像还有数学方法
假设没有整数限制，把数n分成每份大小为x，则共有n/x份，乘积为
f(x)=x^(n/x)
求导得f'(x)= n/(x^2) * x^(n/x) * (1 - lnx)
当f'(x) = 0时，x = e
所以理想情况下是把每份分成e，得到得结果最大。
但这里是整数，所以具体怎么分，还没有想清楚
另外，当p>4时,(p-2)*2-p=p-4>0
当p>9/2时，(p-3)*3-p=2p-9>0
并且2*2*2<3*3
所以当剩下部分大于等于5时，可以尽可能分出3，剩下得要么是2要么是3(5-3=2,6-3=3,7-3=4=2*2, 8-3=5回到第一种情况...)
class Solution {
public int integerBreak(int n) {
if (n == 2) return 1;
else if (n == 3) return 2;
int res = 1;
while (n >= 5) {
res *= 3;
n -= 3;
}
res *= n;
return res;
}
}
