C++/C#/Python leetcode 343. Integer Break

Certainly! Below is a C++ solution for the LeetCode problem 343, "Integer Break". The problem requires you to maximize the product of integers that sum up to a given integer n by breaking it into at least two positive integers.

C++ Code:
#include <iostream>
#include <vector>

class Solution {
public:
    int integerBreak(int n) {
        // Create a dp array to store the maximum product for each integer
        std::vector<int> dp(n + 1, 0);

        // Base case: for integers 1 and 2
        dp[1] = 1; // 1 cannot be broken down
        dp[2] = 1; // 2 can only be broken into 1 + 1

        // Fill the dp array for all integers from 3 to n
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                // Maximize the product by considering breaking i into j and (i - j)
                dp[i] = std::max(dp[i], std::max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
};

int main() {
    Solution solution;

    // Test with some examples
    int n = 10; // Example input
    std::cout << "Maximum product for integer break of " << n << " is: " << solution.integerBreak(n) << std::endl;

    return 0;
}
Explanation:
Dynamic Programming Array: We create a dp array where dp[i] holds the maximum product obtainable by breaking the integer i.
Base Cases:
For n = 1, the only option is 1, hence dp[1] = 1.
For n = 2, the only option is 1 + 1, hence dp[2] = 1.
Filling the DP Array:
For each integer i from 3 to n, we check all possible ways to break i into two parts j and i - j.
We calculate the maximum product by comparing the product of j * (i - j) and j * dp[i - j] to ensure that we also consider previous results stored in the dp array.
Return the Result: Finally, we return dp[n], which contains the maximum product for the integer n.
Example Usage:
You can change the value of n in the main function to test with different inputs. The output will show the maximum product for the integer break of the given n.

Sure! Below is a C# solution for the LeetCode problem 343, "Integer Break". This problem involves breaking an integer n into at least two positive integers such that their product is maximized.

C# Code:
using System;

public class Solution {
    public int IntegerBreak(int n) {
        // Create a dp array to store the maximum product for each integer
        int[] dp = new int[n + 1];

        // Base cases
        dp[1] = 1; // 1 cannot be broken down
        dp[2] = 1; // 2 can only be broken into 1 + 1

        // Fill the dp array for all integers from 3 to n
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // Maximize the product by considering breaking i into j and (i - j)
                dp[i] = Math.Max(dp[i], Math.Max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
}

public class Program {
    public static void Main() {
        Solution solution = new Solution();

        // Test with some examples
        int n = 10; // Example input
        Console.WriteLine($"Maximum product for integer break of {n} is: {solution.IntegerBreak(n)}");
    }
}
Explanation:
Dynamic Programming Array: We create an array dp where dp[i] holds the maximum product obtainable by breaking the integer i.
Base Cases:
For n = 1, the only option is 1, hence dp[1] = 1.
For n = 2, the only option is 1 + 1, hence dp[2] = 1.
Filling the DP Array:
For each integer i from 3 to n, we check all possible ways to break i into two parts j and i - j.
We calculate the maximum product by comparing the product of j * (i - j) and j * dp[i - j] to ensure that we also consider previous results stored in the dp array.
Return the Result: Finally, we return dp[n], which contains the maximum product for the integer n.
Example Usage:
You can change the value of n in the Main method to test with different inputs. The output will show the maximum product for the integer break of the given n. For example, for n = 10, the output will be 36, as the optimal break is 3 + 3 + 4.

Certainly! Below is a Python solution for the LeetCode problem 343, "Integer Break". The goal is to maximize the product of integers that sum up to a given integer n by breaking it into at least two positive integers.

Python Code:
class Solution:
    def integerBreak(self, n: int) -> int:
        # Create a dp array to store the maximum product for each integer
        dp = [0] * (n + 1)

        # Base cases
        dp[1] = 1  # 1 cannot be broken down
        dp[2] = 1  # 2 can only be broken into 1 + 1

        # Fill the dp array for all integers from 3 to n
        for i in range(3, n + 1):
            for j in range(1, i):
                # Maximize the product by considering breaking i into j and (i - j)
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

        return dp[n]

# Example usage
if __name__ == "__main__":
    solution = Solution()

    n = 10  # Example input
    print(f"Maximum product for integer break of {n} is: {solution.integerBreak(n)}")
Explanation:
Dynamic Programming Array: We create a list dp where dp[i] holds the maximum product obtainable by breaking the integer i.
Base Cases:
For n = 1, the only option is 1, hence dp[1] = 1.
For n = 2, the only option is 1 + 1, hence dp[2] = 1.
Filling the DP Array:
For each integer i from 3 to n, we check all possible ways to break i into two parts j and i - j.
We calculate the maximum product by comparing the product of j * (i - j) and j * dp[i - j] to ensure that we also consider previous results stored in the dp array.
Return the Result: Finally, we return dp[n], which contains the maximum product for the integer n.
Example Usage:
You can change the value of n in the if __name__ == "__main__": block to test with different inputs. The output will show the maximum product for the integer break of the given n. For example, for n = 10, the output will be 36, as the optimal break is 3 + 3 + 4.