Skip to content

Instantly share code, notes, and snippets.

@dgroft
Last active December 19, 2015 08:19
Show Gist options
  • Save dgroft/5924594 to your computer and use it in GitHub Desktop.
Save dgroft/5924594 to your computer and use it in GitHub Desktop.
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.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment