Files

907 B
Raw Permalink Blame History

计算和的最大乘积

给定一个正整数n将其拆分为至少两个正整数的和并使这些整数的乘积最大化返回这些加数的最大乘积。

例如10 = 3+3+4结果3x3x4 = 36

问题:如何让加数的乘积最大?

从1到n开始拆解

    1. 1不能拆解

    2. 2 = 1+11

    3. 3 = 2+12

    4. 4 = 2+24不用拆解

    5. 5 = 3+26可以拆解

    6. 6 = 3+39可以拆解

    7. 7 = 3+412可以拆解

    8. 8 = 3+3+218可以拆解······ N. n = 3+3...+x,

规则数字n>4可以将其拆解成n = 3k+x

实现思路(n>4):

    1. n%3 == 1, 3的数量k=(n-4)//3, 结果pow(3, k)x4

    2. n%3 == 2, 3的数量k=n//3, 结果pow(3, k)x(n%3)

    3. n%3 == 0, 3的数量k=n//3, 结果pow(3, k)