最大化兩個整數列表之間的總和？ （有限制）

Question

最近這個給我的是面試問題，我解決得不夠快。

如果您有兩個列表，並且您希望最大化它們之間的總和，但一次只能取一個條目，並且如果要跳轉到另一個列表，您必須跳過一個條目，您將如何做它？

例如，你有兩個城市，洛杉磯和紐約，你可以在兩個城市收錢。您可以前往其他城市，但要做到這一點，您必須跳過一個條目，您將如何最大化您的資金？假設您需要收錢的天數爲< =紐約和洛杉磯（這兩個列表）的天數。

下面是兩個例子列表：

LA：[300，400，800，900]

NY：[829，450，950，300，500，300]

你可以拿300和400.或者，你可以拿300，第二天旅行（跳過400和450），並在紐約950。

你會採取什麼樣的方式給你最大的收益？這是我到目前爲止：

def maximize(n, la_income, ny_income): 
"Assume n <= len(sf_income), n <= len(ny_income)" 
    ny_optimals=defaultdict() 
    la_optimals=defaultdict() 
    for e in range(0,len(sf_income),-1): 
     if la_optimal[e+1]>ny_optimal[e+2]: 
      la_optimal[e]=la_income[e]+la_optimal[e+1] 
     else: 
      la_optimal[e]=la_income[e]+ny_optimal[e+2] 

我想創建兩個最佳收入列表，但這種方式似乎非常unpythonic。什麼是解決這個問題的快速和pythonic方式？

Answer 1

遞歸搜索點如何？

LA = [300, 400, 800, 900] 

NY = [829, 450, 950, 300, 500, 300] 

def search(now, nxt): 
    if len(nxt) < 2: 
     return now 
    elif not now: 
     return nxt[1:] 
    stick = [now[0]] + search(now[1:], nxt[1:]) 
    switch = search(nxt[1:], now[1:]) 
    return max((stick, switch), key=sum) 

print(search(LA, NY)) 

正如roippi在評論中指出的那樣，memoization會提高性能。