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.

分析

其实这是一道数学题。假设最终的值是 f，分割的数可以不是整数，设为 m，有：$f=m^{\frac{n}{m}}$，两边取对数，有$lnf=\frac{n}{m}lnm$，两边同时对 m 求导，有：$\frac{f^{‘}}{f}=n\frac{1-lnm}{m^{2}}$，可知，当 m=e=2.718…时取最大值，m=3 与 e 最接近，分割的数为整数，可以取3。

再换个角度思考，分割出的数字大于4是不行的，因为假设分割出了m，m 可以分割为 m-2 和 2，而$(m-2)*2>m$，$m=4$ 时，$m=2*2=2+2$，因此只需要比较2和3两个数，假设$n=3*m+2*n$，$f=3^{m}+2^{n}=3^{m}+2^{\frac{n-3*m}{2}}$，两边取对数，有：$lnf=mln3+\frac{x-3m}{2}ln2=\frac{x}{2}ln2+(ln3-\frac{3}{2}ln2)m$，$ln3-\frac{3}{2}ln2$ 是大于0的，m 越大，f 越大，因此 m 取3。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int integerBreak(int n) {
        if(n == 2) {
            return 1;
        }
        if(n == 3) {
            return 2;
        }
        int res = 1;
        while(n > 4) {
            n -= 3;
            res *= 3;
        }
        return res * n;
    }
};

相关问题

题目来源