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?
Octave solution
Linear time, constant space
function total = nonadjacent_sum(weight_vector)
total = 0;
alternate_sum = zeros(2, 1);
for i = 1:numel(weight_vector)
parity = mod(i, 2) + 1;
if alternate_sum(3 - parity) > alternate_sum(parity) + weight_vector(i)
total += alternate_sum(3 - parity);
alternate_sum = zeros(2, 1);
elseif weight_vector(i) > 0
alternate_sum(parity) += weight_vector(i); end; end;
total += max(alternate_sum); end;
c++ solution
@Absinthe C++ is clearly not the appropriate tool, but I need to refamiliarize myself with it, so thanks for the excercise. Solution: https://gitlab.com/tymorl/warmups/blob/master/nonadjecentSum/sol.cpp .
c++ solution
@zingbretsen @Absinthe Thanks! I forgot repos created on gitlab are private by default, shoud be public now. :)
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.
Okay, here is my try in python
https://git.qoto.org/Absinthe/nonadjacentsum