Daily Coding Problem - 9

day-9.py

"""
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?
"""
def largestSum(arr):
    if len(arr) == 0:
        return 0 
    if len(arr) == 1:
        return arr[0]
    # 2 possibilities for each element:
    # Either we include the element or don't
    # If we include the element, then we exclude the immediate next element
    return max(arr[0] + largestSum(arr[2:]), largestSum(arr[1:]))

print(largestSum([2, 4, 6, 2, 5])) # 13
print(largestSum([5, 1, 1, 5])) # 10