<jupyter_start><jupyter_text>Daily Coding Problem: Problem 9 [Hard]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?<jupyter_code>def find_max_sum(arr):
    incl = 0
    excl = 0
    
    if len(arr) == 2:
        # the arr has 2 elements and since they are adjacent we can't add them --> highest sum == 0
        return 0
    
    for i in arr:
        new_excl = max(incl, excl)
        incl = excl + i
        excl = new_excl
    return max(incl, excl)
arr = [5,  5, 10, 40, 50, 35] 
print(find_max_sum(arr))
assert find_max_sum([5, 5, 10, 100, 10, 5]) == 110
assert find_max_sum([5,  5, 10, 40, 50, 35]) == 80<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12643678160919541, 'fraction_numerical': 0.06374085684430512, 'mean_word_length': 3.1293103448275863, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '183215', 'license': 'MIT', 'n_tokens_mistral': 391, 'n_tokens_neox': 347, 'n_words': 137, 'path': 'problem_#9.ipynb', 'repo_name': 'KuniXl/daily_coding_problems', 'size': '957'}