Given an array 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.
[5, 20, 15, -2, 18] => 20 + 18 = 38
[4, 1, 6, 3, 2] => 4 + 6 + 2 = 12
Follow-up: Can you do this in O(N) time and constant space?
All such questions can be seen all over the Internet, just do Google search a little & one can solve these questions. Below is kind of same -
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.
[5, 20, 15, -2, 18] => 20 + 18 = 38
[4, 1, 6, 3, 2] => 4 + 6 + 2 = 12
Follow-up: Can you do this in O(N) time and constant space?
All such questions can be seen all over the Internet, just do Google search a little & one can solve these questions. Below is kind of same -
NonAdjacentSum
NonAdjacentSum(2)