343. Integer Break

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

1. 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.
2. 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: - The product of j and i-j. - The product of 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].
3. Final Result: Once the table is filled, the value of dp[n] will give the maximum product obtainable by breaking n.

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]
};