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.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: you may assume that n is not less than 2.
My Solution
代码的run time是1ms，时间复杂度是，空间复杂度是。
public class Solution {
public int integerBreak(int n) {
int[] records = new int[n];
records[0] = 1; // 2
for (int i = 3; i <= n; ++i) {
int max = 0;
for (int j = i / 2; j < i; ++j) {
int jPair = i - j;
int prod = 0;
if (j <= 4) {
if (jPair <= 4) {
prod = j * jPair;
} else {
prod = j * records[jPair - 2];
}
} else {
if (jPair <= 4) {
prod = records[j - 2] * jPair;
} else {
prod = records[j - 2] * records[jPair - 2];
}
}
max = (max > prod) ? max : prod;
}
records[i - 2] = max;
}
return records[n - 2];
}
}
Analysis
这道题事实上有一个时间复杂度为的解，我不是很理解其中的数学原理，但可以举几个例子试出来。
public class Solution {
public int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
int[] records = new int[n + 1];
records[2] = 2;
records[3] = 3;
for (int i = 4; i <= n; ++i) {
records[i] = Math.max(records[i / 2] * records[i - i / 2],
Math.max(records[i - 2] * 2, records[i - 3] * 3));
}
return records[n];
}
}
Description
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.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: you may assume that n is not less than 2.
My Solution
代码的run time是1ms，时间复杂度是
，空间复杂度是
。
Analysis
这道题事实上有一个时间复杂度为
的解，我不是很理解其中的数学原理，但可以举几个例子试出来。