907 B
907 B
计算和的最大乘积
给定一个正整数n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化,返回这些加数的最大乘积。
例如:10 = 3+3+4,结果3x3x4 = 36
问题:如何让加数的乘积最大?
从1到n开始拆解:
1. 1不能拆解;
2. 2 = 1+1,积:1
3. 3 = 2+1,积:2
4. 4 = 2+2,积:4,不用拆解
5. 5 = 3+2,积:6,可以拆解
6. 6 = 3+3,积:9,可以拆解
7. 7 = 3+4,积:12,可以拆解
8. 8 = 3+3+2,积:18,可以拆解;······ 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)