Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

Daily_coding_Problem_9.py

'''
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.
'''
def max_sum_non_adjacent(nums):
    if len(nums)==0:
        return 0
    if len(nums)==1:
        if nums[0]<=0:
            return 0
        else:
            return nums[0]
    if len(nums)==2:
        return max(0,max(nums[0],nums[1]))
    incl=max(0,nums[0])
    excl=max(0,nums[1])
    for i in range(2,len(nums)):
        prev_incl=incl
        incl=max(incl,incl+nums[i])
        excl=max(prev_incl,excl)
        incl,excl=excl,incl
    return max(excl,incl)