A flower seller parks her cart in one of two spots each day: outside the train station or by the park gates. From past sales she knows what she would earn at each spot on each day: station[i] and park[i] for day i. Moving the cart between spots overnight costs move_fee. On day 0 she can start at either spot for free, and staying put costs nothing.
Implement best_earnings(station: list[int], park: list[int], move_fee: int) -> int: the most she can earn over all the days, after paying for every move.
best_earnings([5, 1, 5], [1, 6, 1], 4) # 11 stay at the station all three days
# (chasing the park on day 1 earns 5+6+5 but pays 8 in fees)
best_earnings([3, 3, 3, 3], [1, 9, 9, 1], 2) # 20 e.g. station, park, park, station: 24 - 4
Picking the better spot each day on its own is not enough, as the first example shows.
Constraints: len(station) == len(park), 0 <= len(station) <= 100_000, 0 <= station[i], park[i], move_fee <= 10_000. With no days the answer is 0. Trying all 2^n spot sequences is hopeless; aim for O(n).
Show hint
keep two running values, the best total for days 0..i if she ends day i at the station and the best if she ends it at the park; each day's value is that day's earnings plus the better of "was already here" and "was at the other spot, minus move_fee".