Here's a freebie,
This problem was asked by Airbnb.
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.
For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.
Follow-up: Can you do this in O(N) time and constant space?
Python solution
@Absinthe #toyprogrammingchallenge
https://git.qoto.org/zingbretsen/nonadjacent_sums/blob/master/main.py
This solution modifies the list as we loop over it. It ensures that at each step, we have the maximum possible sum at each step.
The possibility of having negative numbers necessitates checking at each step.
O(N) time, and repurposes the original list for calculations, so adds no space overhead. This could also be done with a separate 2-item register if the original list should not be modified. This would also be constant space.
