Java DP solution with Explanation


  • 1
    I

    The idea here is to assign an array which length is n+1, and this array stores maximum products along with its index. Eg:

    index: 0 1 2 3 4 5
    value: 0 0 1 2 4 6

    These values of the array is assigned dynamically. When we want to know the maximum product of 7, firstly, here the outer loop "i" equals 7, and it goes inner loop.
    (1) "j" begins with value 1, we compare 1 and array[1] and get the maximum one(which is 1 not 0 coz we don't want to break 1 into (0+1)), and the result product is 1 * 6 = 6.
    (2) "j" = 2, we compare 2 and array[2],we got 2(coz we don't want to break 2 into (1+1) otherwise the product is smaller). the product is 2 * 5 = 10 and it is larger than the result we got in (1) which is 6. So, currently, the result is 10.
    .......

    until we find the maximum product it will stop.

    public class Solution {
         public int integerBreak(int n) {
            
            int[] table = new int[n+1];
            table[0] = 0;
            for(int i = 1;i < table.length;i++){
                    table[i] = 0;
                for(int j = 1;j < i;j++){
                    int max = Math.max(j,table[j]);
                    table[i] = Math.max((max * (i-j)),table[i]);
                }
            }
            
            return table[n];
        }
    }
    

  • 0
    I
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.