Dare2Solve
The problem asks to find the maximum product that can be obtained by breaking a positive integer n
into at least two positive integers and multiplying them together. You need to return this maximum product.
The key observation here is that breaking the integer n
into smaller integers gives more opportunities to maximize the product. This problem can be approached using dynamic programming to store and update the best product we can get for each integer from 1
to n
.
Dynamic Programming Setup:
We create a dp
array where dp[i]
represents the maximum product obtainable by breaking the integer i
. We initialize dp
with 1
as any integer can be at least broken down into 1.
Iterative Calculation:
For each number i
from 3
to n
, we try breaking it into two parts: j
and i-j
. For each j
, we consider:
j
and i-j
.j
and the best product of i-j
(which is stored in dp[i-j]
).We update dp[i]
by taking the maximum of the current value, the product j * (i-j)
, and j * dp[i-j]
.
Final Result:
Once the table is filled, the value of dp[n]
will give the maximum product obtainable by breaking n
.
O(n^2)
We loop through numbers from 1
to n
, and for each number, we loop through potential partitions, making this a quadratic time solution.
O(n)
We use an array dp
of size n+1
to store the maximum products for each integer from 1
to n
.
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], dp[i - j] * j, (i - j) * j});
}
}
return dp[n];
}
};
class Solution:
def integerBreak(self, n: int) -> int:
dp = [1] * (n + 1)
for i in range(3, n + 1):
for j in range(1, i):
dp[i] = max(dp[i], dp[i - j] * j, (i - j) * j)
return dp[n]
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, 1);
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
}
}
return dp[n];
}
}
var integerBreak = function (n) {
const dp = Array(n + 1).fill(1)
for (let i = 3; i <= n; i++) {
for (let j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)
}
}
return dp[n]
};