40. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Solution: (Recursion)

// Solution 1 : 
class Solution
{
public:
    long long int maxProd = 0;

    void findMax(int sum, long long int prod, int num, int count, int maxNum)
    {
        if (sum == 0 && count >= 2)
        {
            maxProd = max(prod, maxProd);
            return;
        }

        if (sum < 0)
        {
            return;
        }

        if (num > maxNum)
        {
            return;
        }

        findMax(sum, prod, num + 1, count, maxNum);
        findMax(sum - num, prod * num, num, count + 1, maxNum);

        return;
    }

    int integerBreak(int n)
    {
        findMax(n, 1, 1, 0, n);
        return maxProd;
    }
};




// Solution 2 : 
class Solution
{
public:
    long long int maxProd = 0;

    void findMax(int sum, long long int prod, int count)
    {
        if (sum == 0 && count >= 2)
        {
            maxProd = max(prod, maxProd);
            return;
        }

        if (sum < 0)
        {
            return;
        }

        for (int i = 1; i <=sum; i++)
        {
            findMax(sum - i, prod * i, count + 1);
        }

        return;
    }

    int integerBreak(int n)
    {
        findMax(n, 1, 0);
        return maxProd;
    }
};

Solution: (Recursion + Memo)

//Solution:1
class Solution
{
public:
    int findMax(int sum, int num, int count, int maxNum, vector<vector<int>> &dp)
    {
        if (sum == 0 && count >= 2)
        {
            return 1;
        }

        if (sum < 0)
        {
            return 0;
        }

        if (num > maxNum)
        {
            return 0;
        }

        if (dp[count][sum] != -1)
        {
            return dp[count][sum];
        }

        int inc = findMax(sum, num + 1, count, maxNum, dp);
        int exc = num * findMax(sum - num, num, count + 1, maxNum, dp);

        dp[count][sum] = max(inc, exc);
        return max(inc, exc);
    }

    int integerBreak(int n)
    {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
        return findMax(n, 1, 0, n, dp);
    }
};



//Solution:2
class Solution
{
public:
    int findMax(int sum, int count, vector<int> &dp)
    {
        if (sum == 0 && count >= 2)
        {
            return 1;
        }

        if (sum < 0)
        {
            return 0;
        }

        if (dp[sum] != -1)
        {
            return dp[sum];
        }

        int val = 0;

        for (int i = 1; i <= sum; i++)
        {
            val = max(val, i * findMax(sum - i, count + 1, dp));
        }

        dp[sum] = val;

        return val;
    }

    int integerBreak(int n)
    {
        vector<int> dp(n + 1, -1);
        int maxProd = findMax(n, 0, dp);
        return maxProd;
    }
};

Solution: (DP)

class Solution
{
public:
    int integerBreak(int n)
    {

        vector<int> dp(n + 1, 1);

        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for (int i = 3; i <= n; i++)
        {

            for (int j = 1; j < i; j++)
            {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
            
        }

        return dp[n];
    }
};