343. Integer Break, leetcode - dynamic programming

May 23, 2020 — 1 Min Read

Another interesting leetcode problem that comes up often in Apple and Google interviews.

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

We have solved this problem using recursion before, please visit this page for more details

Here is our recursive solution and we will rewrite it iteratively afterwards.

class Solution {
    private final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    public int integerBreak(int n) {   
        // check if we know the result already
        if(map.containsKey(n)) {
           return map.get(n);
        }
        if(n == 2) {
            return 1;
        }
        
        var max = Integer.MIN_VALUE;
        
        for(int i = 1; i < n; i++) {
            var firstBreak = Math.max(i, integerBreak(i));
            var secondBreak = Math.max(n - i, integerBreak(n-i));
            
            max = Math.max(max, firstBreak * secondBreak);
        }
        
        // store maximum
        map.put(n, max);
        
        return max;
    }
}

And here comes bottom-up iterative DP approach.

Create an array DP to store results, similar to map in the recursive method. The only difference is that indexes play the role of the keys and each index corresponds to an N. DP[10] would be result for N = 10
Start from 2, our base, and calculate every combination.

class Solution {
    
    public int integerBreak(int n) {   
        var dp = new int[n+1];

        for(int i = 2; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                var firstBreak = Math.max(j, dp[j]);
                var secondBreak = Math.max(i - j, dp[i - j]);
                dp[i] = Math.max(dp[i], firstBreak * secondBreak);
            }
        }
        return dp[n];
    }