Maximize the sum of a given collection such that if you include the number in sum, you may not use adjacent numbers toward the sum. For the collection [1, 5, 3, 9, 4], the max sum is 5 + 9 = 14. For the collection [1, 2, 3, 4, 5], the max sum is 1 + 3 + 5 = 9. For the collection [1, 3, 5, -1, 12, 6, 7, 11], the max sum is 1 + 5 + 12 + 11 = 29.

maxsumnonadjacent.py

from __future__ import print_function
import heapq

# construct initial collection
initial_col = [1, 5, 3, 9, 4]

# construct heap
heap = []

# assemble the heap, store tuples as such: (original_value, original_index)
for index, value in enumerate(initial_col):
    heapq.heappush(heap, (value * -1, index))

# keeps record of used indexes (a list of booleans, each initialized to False)
used_indexes = map(lambda x: False, initial_col)

# will hold all highest, non-adjacent nums
highest_nums = []

# empty the heap, populate list that holds highest, non-adjacent nums
while (heap):
    t = heapq.heappop(heap)
    left_idx = t[1] - 1
    right_idx = t[1] + 1
    if left_idx > -1 and left_idx < len(used_indexes) and used_indexes[left_idx] == True: continue
    if right_idx > -1 and right_idx < len(used_indexes) and used_indexes[right_idx] == True: continue
    used_indexes[t[1]] = True
    highest_nums.append(t[0]*-1)

# calculate the total (i know about sum(), but reduce() w/ lambda was more fun)
total = reduce(lambda x, y: x + y, highest_nums)

print("total: %d" % total)