高中数学也能解决阿里面试算法题？

大家好，我是新熊君。

今天跟大家分享一道阿里的算法面试题。

题目描述

给定一个正整数n，把它拆分为若干个数的和，记这若干个数的积为M，求M的最大值。

题目分析

这道题正常的思路是使用动态规划算法。

假设 dp[n] 为正整数 n 拆分后能够得到最大的积。

状态转移时只需要遍历小于n的每一个正整数 k ，

取 k*dp[i-k] 的最大值，即：

dp[n] = max(n, max(k * dp[i-k]))
k \in (0, i)

时间复杂度O(n^2)，空间复杂度O(n)

进一步分析

假设把n个数拆分成k个数之和，乘积为M，有：

n = \sum_{i=1}^k x_i
M = \prod_{i=1}^k x_i

由均值不等式：

\sqrt[k]{x_1x_2...x_k} \leq \frac{x_1+x_2...+x_k}{k}

将M和n代入上式得：

M \leq (\frac{n}{k})^k

故本质是求(\frac{n}{k})^k的最大值。

两边同时取对数，得：

ln(M) \leq k \ ln(\frac{n}{k})

令：
f(k) = k \ ln(\frac{n}{k})

求导后得到：

f'(k) = ln(\frac{n}{k}) - 1

则当k = n/e时取得最大值

因为e的值与3最接近，所以最终得到一个优化的算法：

先对n尽可能多地拆分3：

如果剩余的数为2或0，则拆分结束。

如果剩余的数为1，则将拆分好的3拿一个与剩余的1组合拆分成两个2。

此题得解。

只需要使用快速幂求一下幂次即可，

时间复杂度O(log n)，空间复杂度 O(1)。

用高中数学就解决了这道面试算法题。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容