hackerrank-max-array-sum.py

# Create an array to track the max sum
# The max could be either the current value, the current max, or the current value plus the max of arr[i-2]

def maxSubsetSum(arr):
    maxTop = max(arr[0], arr[1])
    maxes = [arr[0], maxTop]

    for i in range(2, len(arr)):
        localMax = max(max(arr[i], maxTop), maxes[i-2]+arr[i])
        maxes.append(localMax)
        maxTop = max(maxTop, localMax)
    return maxTop