LeetCode题解 343.Integer Break

题目：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.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

解释：

先看个穷举的规律，本题最核心的技巧或者说思路是 将数字拆分成2和3的乘积，因为 2*3 > 1*5; 3*3 > 1*6; 3*2*2 > 1*7; 2*2*2*2 > 1*8 .......所以拆分成2和3后，就能得到最大的乘积。

2 ：1 , 1

3 ：1 , 2

4 ：2 , 2

5 ：3 , 2

6 ：3 , 3

7 ：3 , 2 , 2

8 ：3 , 3 , 2

9 ：3 , 3 , 3

10 ：3 , 3 , 2, 2

代码：

public class Solution {
　　public int integerBreak(int n) {
　　　　if (n == 2) return 1;
　　　　if (n == 3) return 2;
　　　　if (n % 3 == 0) return (int)Math.pow(3, n / 3);
　　　　if (n % 3 == 1) return (int)Math.pow(3, (n - 4) / 3) * 4; // 有多少的3和4可以根据上面的穷举找到规律
　　return (int)Math.pow(3, (n - 2) / 3) * 2;
　　}
}

巴特西

LeetCode题解 343.Integer Break

最新文章

热门文章