python - Maximize the sum between two lists of integers? (with restrictions) -

python - Maximize the sum between two lists of integers? (with restrictions) -

recently given me interview question couldn't solve fast enough.

if have 2 lists, , want maximize sum between them, can take 1 entry @ time , if want jump other list, have skip entry, how it?

for example, have 2 cities, la , new york, , can collect money in both cities. can travel other city have skip 1 entry, how maximize money? assuming number of days have collect money <= number of days in ny , la (the 2 lists).

here 2 illustration lists:

la: [300, 400, 800, 900]

ny: [829, 450, 950, 300, 500, 300]

you can take 300 , 400. or, can take 300, travel next day (skipping 400 , 450) , take 950 in ny.

what path take give greatest sum? have far:

def maximize(n, la_income, ny_income): "assume n <= len(sf_income), n <= len(ny_income)" ny_optimals=defaultdict() la_optimals=defaultdict() 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]

i'm trying create 2 lists of optimal incomes way seems unpythonic. quick , pythonic way solve problem?

how spot of recursive searching?

la = [300, 400, 800, 900] ny = [829, 450, 950, 300, 500, 300] def search(now, nxt): if len(nxt) < 2: homecoming elif not now: homecoming nxt[1:] stick = [now[0]] + search(now[1:], nxt[1:]) switch = search(nxt[1:], now[1:]) homecoming max((stick, switch), key=sum) print(search(la, ny))

as roippi points out in comments, memoization improve performance.

python algorithm