343. Integer Break.md

343. Integer Break

---

leetcode-cn Daily Challenge on July 30th, 2020.

---

Difficulty : Medium

Related Topics : Math、Dynamic Programming

---

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.

Example 1:

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

Example 2:

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

Note

• You may assume that n is not less than 2 and not larger than 58.

---

Solution

• mine
  • Java
    • Dynamic Programming Runtime: 1 ms, faster than 56.03%, Memory Usage: 36.6 MB, less than 6.10% of Java online submissions

      // O(N^2)time
      // O(N)space
      public int integerBreak(int n) {
          if(n < 3){
              return 1;
          }
          // dp[i] = max(dp[i - j] * j, (i - j) * j)
          int[] dp = new int[n + 1];
          dp[1] = dp[2] = 1;
          for(int i = 3;  i <= n; i++){
              for(int j = 1;  j < i; j++){
                  dp[i] = Math.max(dp[i], dp[i- j] * j);
                  dp[i] = Math.max(dp[i], (i- j) * j);
              }
          }
          return dp[n];
      }
      

---

• the most votes

• Math Runtime: 0 ms, faster than 100.00%, Memory Usage: 36 MB, less than 57.32% of Java online submissions

  // O(1)time
  // O(1)space
  public int integerBreak(int n) {
      if(n < 4){
          return n - 1;
      }
      int r = n / 3;
      int m = n % 3;
      if(m == 0){
          return (int)Math.pow(3, r);
      }else if(m == 1){
          return (int)Math.pow(3, r - 1) * 4;
      }else{
          return (int)Math.pow(3, r) * 2;
      }
  }
  

---