Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
class BadNeighbours:
def maxDonations(self, donations):
L = len(donations)
if L < 3:
return max(donations)
# memo1[L-2] will have maximum value of donations which
# *may* include the first neighbour (therefore cannot include
# the last neighbour)
# memo2[L-1] will have the maximum value of donations
# which do not include the first neighbour (and therefore
# can include the last neighbour)
memo1, memo2 = [0]*L, [0]*L
memo1[0], memo2[0] = donations[0], 0
memo1[1], memo2[1] = donations[1], donations[1]
memo1[2], memo2[2] = donations[2] + memo1[0], donations[2] + memo2[0]
for n in range(3, L):
memo1[n] = max(memo1[n-2] + donations[n], memo1[n-3] + donations[n])
memo2[n] = max(memo2[n-2] + donations[n], memo2[n-3] + donations[n])
return max(memo1[L-2], memo2[L-1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.