The topic of dry

Given a positive integer n, split it into the sum of at least two positive integers and maximize the product of these integers. Returns the largest product you can get.

Example 1:

Input: 2 Output: 1 Description: 2 = 1 + 1, 1 × 1 = 1.Copy the code

Example 2:

Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.Copy the code

Note: You can assume that n is not less than 2 and not greater than 58.

Solution: dynamic programming

The splitting of each digit can be divided into two cases, one is the result of splitting directly, and the other is the result of splitting the other half of the divisible part, so we let dp[I] mean the largest number that array I can split.

A number can take apart from I = 2, because the 0 s and 1 s no longer split range, then the other half of the j is split, which can calculate the result of the break up, we only need to take them split and split the maximum value distribution, pick them and we use this value is stored in the current cycle before the maximum sumCurrent comparison, The final maximum is assigned to dp[I].

By doing this round and round, you can calculate the maximum number of disassembly slots in a given array. And the first one depends on the second one. Finally, return dp[n].

Code implementation:

Execution time: 88 ms=, beating 49.13% of all JavaScript commits

Memory consumption: 37.7 MB, beating 76.31% of all JavaScript commits

 var integerBreak = function (n) {
    let dp = new Array(n).fill(0);
    for (let i = 2; i <= n; i++) {
      let maxCurrnet = 0;
      for (let j = 1; j < i; j++) {
        maxCurrnet = Math.max(maxCurrnet, Math.max(j * (i - j), j * dp[i - j]))
      }
      dp[i] = maxCurrnet
    }
    return dp[n]
  };
Copy the code