leetcode343.Integer Break

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
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 and not larger than 58.

将一个正整数分解为两个或两个以上的正整数，要求这些正整数的乘积最大。

思路和代码

这里应用了一个数学的思路。假设我们有一个数字n，该数组可以随机分解为t和n-t。当分解为n/2时可以获得最大的乘积。因此t取n/2时可以得到最好的结果。但是这里我们明显还可以继续对t分解（如果t大于1），这样逐个分解之后终归会分解为2或者1为质因数

假设N为偶数，(N/2)*(N/2)>=N, 则 N>=4
假设N为奇数，(N-1)/2 *(N+1)/2, 则 N>=5

因此分解的数小于4。

至于为什么我们需要尽可能用3分解，因为3*3>2*2*2。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int integerBreak(int n) {
    if(n == 2) return 1;
    if(n == 3) return 2;
    
    int product = 1;
    while(n >4){
        product *= 3;
        n -= 3;
    }
    
    product *= n;
    return product;
}