🎨Now live: Try our Free AI Image Generation Feature

Description
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.
Intuition
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
.
Approach
- Dynamic Programming Setup:
We create a
dp
array wheredp[i]
represents the maximum product obtainable by breaking the integeri
. We initializedp
with1
as any integer can be at least broken down into 1. - Iterative Calculation:
For each number
i
from3
ton
, we try breaking it into two parts:j
andi-j
. For eachj
, we consider: - The product ofj
andi-j
. - The product ofj
and the best product ofi-j
(which is stored indp[i-j]
). We updatedp[i]
by taking the maximum of the current value, the productj * (i-j)
, andj * dp[i-j]
. - Final Result:
Once the table is filled, the value of
dp[n]
will give the maximum product obtainable by breakingn
.
Complexity
Time Complexity:
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.
Space Complexity:
O(n)
We use an array dp
of size n+1
to store the maximum products for each integer from 1
to n
.
Code
C++
class Solution {
public:
int integerBreak(int n) {
vector 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];
}
};
Python
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]
Java
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];
}
}
JavaScript
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]
};