前言

今天參加了攜程的筆試，編程題第一題一開始想錯了方向，花費了很多時間（雖然第二題就是給時間也不一定做得出來，(⊙﹏⊙)b）。

下面記錄一下這個小插曲。

正文

題目要求

將指定的正整數(shù)n分解成若干個互不相同的自然數(shù)的和，且使這些自然數(shù)的乘積最大

人家給了個輸入輸出的例子，如下：

輸入15

輸出 144

言下之意就是在自然數(shù)之和為15的這些數(shù)字中，乘積最大的一對是

2 3 4 6

思路

為了使得這些自然數(shù)之和的乘積最大，那么這些數(shù)字應該盡可能的接近。

下面舉幾個小例子：

n=10

2+3+4 = 9
// 剩下的那個1補到4上面
2+3+5 

這個時候最大的乘積變成了30

n = 18

2+3+4+5 = 14
//按照剛才的思路， 剩下的4 添加到5上面
2+3+4+9

此時最大的乘積結(jié)果為216

那么這時的結(jié)果是最大的嗎？

答案是否定的，因為剛才是從下標為2開始的。如果下標從3，從4開始呢，我們來看下效果。

3+4+5+6 -->> 最大結(jié)果為：360

4+5+6+7>18則進行去尾加和
4+5+9  -->> 最大結(jié)果為： 180

剩下的其實就不用考慮了。

核心

經(jīng)過剛才的鋪墊，這下不難理解了。最笨的方法就是不斷的遞增下標，然后記錄每一個下標對應的最大值。存儲起來，然后找到這些最大值中最大的那個，就是我們要求的結(jié)果了。

代碼如下：

def mutl(ls):
    result = 1
    for item in ls:
        result *= item
    return result

def compute(n, step):
    path = []
    cursum = 0
    for index in range(step, n):
        if cursum > n:
            last = path.pop()
            path.append(path.pop() + n - (cursum - last))
            break
        path.append(index)
        cursum += index
    return mutl(path)

def my(n):
    total = []
    maxvalue = 0
    for step in range(int(n/2)):
        item = compute(n, step)
        total.append(item)
    maxvalue = max(total)
    return maxvalue



n = 15
result= my(n)
print(result)

運行結(jié)果：

144

測試

再來多測幾組數(shù)據(jù)。

• n=10

30

• n=18

360

這下，可以啦。需要注意的是：

遞增下標到n的一半的位置就可以了，否則結(jié)果會不正確，這是因為計算每次的step的時候會把第一個給算進去，所以導致結(jié)果偏大。

總結(jié)

就攜程的筆試題而言，前面部分的問答題和選擇題還算是中規(guī)中矩，比較偏重于理論和實踐。

編程題就真的是考驗算法的了。大部分的筆試題都是動態(tài)規(guī)劃類型的。我本人比較偏重于開發(fā)方向，所以參加這種筆試題真的是有點力不從心。

不管怎么說，算法是很有必要的。多學點，肯定沒錯，說不一定以后就用得到了。

我， 還有很長的路要走啊。