Skip to content

Instantly share code, notes, and snippets.

@Hydrotoast

Hydrotoast/non_adjacent.py

Created January 14, 2015 19:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Hydrotoast/ed7f4ec43eb7df2dbe00 to your computer and use it in GitHub Desktop.
Save Hydrotoast/ed7f4ec43eb7df2dbe00 to your computer and use it in GitHub Desktop.
Download ZIP
Find the max sum without using any adjacent indeces of the array.
Raw
non_adjacent.py
A = [8,1,3,4,5,10]
ans = 22
def non_adjacent_sum(A):
# Small cases
if len(A) < 3:
return max(A)
# Base cases
prev_prev, prev = A[0], A[1]
curr = max(A[2] + prev_prev, prev)
# Recursive cases
for i in range(3, len(A)):
prev_prev, prev = max(prev_prev, prev), curr
curr = A[i] + prev_prev
return max(curr, prev)
print(non_adjacent_sum(A) == ans)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment