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;
