整数成绩最大化

[编程题]整数成绩最大化

热度指数：2620 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个整数n，将n分解为至少两个整数之和，使得这些整数的乘积最大化，输出能够获得的最大的乘积。

例如：

2=1+1，输出1；

10=3+3+4，输出36。

输入描述:

输入为1个整数

输出描述:

输出为1个整数

示例1

输入

输出

算法知识视频讲解

Python

Jancydc

def solution(n):
    if n<=3:return n-1
    if n==4:return n
    if n>4:
        if n % 3 ==2:
            return 2 * 3**(n//3)
        elif n %3 ==1:
            return 4*3**(n//3-1)
        else:
            return 3**(n//3)
if __name__ =='__main__':
    n = int(input().strip())
    print(solution(n))

这是一道找规律的题

n 1 2 3 4 5 6 7 8 9 10 ...

max 0 1*1 1*2 2*2 2*3 3*3 2*2*3 2*3*3 3*3*3 2*2*3*3 ...

编辑于 2020-06-23 11:12:40 回复(0)

Python

冉龙宇

动态规划问题

n = int(input().strip())
# 动态规划算法
maxli = [0, 1, 1]  # 存储每个数最大的乘积

for num in range(3, n+1, 1):
    maxnum = 0
    l = 1
    r = num-1
    while l<=r:
        maxnum = max(max(l, maxli[l])*max(r, maxli[r]), maxnum)
        l += 1
        r -= 1
    maxli.append(maxnum)

print(maxli[n])

编辑于 2019-08-30 14:23:05 回复(0)

Python

fighting@SHU

#把数字尽可能的拆成3，图片是盗用的。。。  import numpy
aa=int(input())
lst=[]
if aa==2:
    print('1')
elif aa==3:
    print('2')
else:
    while(aa>4):
        lst.append(3)
        aa-=3
    lst.append(aa)
    print(numpy.prod(lst))

发表于 2019-04-19 15:41:36 回复(0)

Python

TimeMac

解释：最大收益是3，余数为1则分给其中一个3,得到4，余数为2则乘上去
所以只需要列举出递推的前三项，第4、5、6项，然后递推a[i]=a[i-3]*3
为什么不是最大收益不是4以上呢？例如5，5可分解为2*3收益能通过继续分解得到增加。
前几个并不能通过递推公式得到，所以列举出来。

1. num = int(input())
2. resultList = [0,0,1,2,4,6,9]
3. if num<7:
4.     print(resultList[num]) 
5. else:
6.     for i in range(7,num+1):
7.         resultList.append(resultList[i-3]*3) 
8. print(resultList[num])

编辑于 2018-09-15 23:45:24 回复(3)