大家好,我是新熊君。 今天跟大家分享一道阿里的算法面试题。 题目描述 给定一个正整数nnn,把它拆分为若干个数的和,记这若干个数的积为MMM,求MMM的最大值。 题目分析 这道题正常的思路是使用动态规划算法。 假设 dp[n]dp[n]dp[n] 为正整数 nnn 拆分后能够得到最大的积。 状态转移时只需要遍历小于nnn的每一个正整数 kkk , 取 k∗dp[i−k]k*dp[i-k]k∗dp[i−k] 的最大值,即: dp[n]=max(n,max(k∗dp[i−k]))dp[n] = max(n, max(k * dp[i-k]))dp[n]=max(n,max(k∗dp[i−k]))