Leetcode 343. Integer Break

Seawolf

1. 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.
   
2. 
   
3. Example 1:
   
4. 
   
5. Input: 2
   
6. Output: 1
   
7. Explanation: 2 = 1 + 1, 1 × 1 = 1.
   
8. Example 2:
   
9. 
   
10. Input: 10
    
11. Output: 36
    
12. Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
    
13. Note: You may assume that n is not less than 2 and not larger than 58.

复制代码

1. 给定一个正整数n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: 2
   
6. 输出: 1
   
7. 解释: 2 = 1 + 1, 1 × 1 = 1。
   
8. 示例2:
   
9. 
   
10. 输入: 10
    
11. 输出: 36
    
12. 解释: 10 = 3 + 3 + 4, 3 ×3 ×4 = 36。
    
13. 说明: 你可以假设n不小于 2 且不大于 58。

复制代码

1. class Solution:
   
2.     def integerBreak(self, n: int) -> int:
   
3.         if n == 2 or n == 3:
   
4.             return n - 1
   
5.         res = 1
   
6.         while n > 4:
   
7.             n = n - 3
   
8.             res = res * 3
   
9.         return res * n

复制代码

Why factor 2 or 3? The math behind this problem.