Skip to content

Instantly share code, notes, and snippets.

@accakks
Created June 12, 2020 19:38
Show Gist options
  • Save accakks/c6747fcb1bef64ab62ddb16f133e7c24 to your computer and use it in GitHub Desktop.
Save accakks/c6747fcb1bef64ab62ddb16f133e7c24 to your computer and use it in GitHub Desktop.
Dynamic solution to max rob amount problem
'''
You are a professional robber planning to rob houses along a street. Each house has
a certain amount of money stashed, the only constraint stopping you from robbing each
of them is that adjacent houses have security systems connected and it will
automatically contact the police if two adjacent houses were broken into on the
same night.
Given a list of non-negative integers representing the amount of money of each house,
determine the maximum amount of money you can rob tonight without alerting the
police.
'''
def max_rob_amount(nums):
"""Function to calculate maximum amount that can be stolen"""
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
rob_house_i = 0
leave_house_i = 0
for i in nums:
'''Note that leave_house_i means previous ith value we left'''
rob_house_i, leave_house_i = leave_house_i + i, max(rob_house_i, leave_house_i)
return max(rob_house_i, leave_house_i)
"""Enter the input as a series of space seperated numbers"""
nums = list(map(int,input().split()))
print(max_rob_amount(nums))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment