Created
June 12, 2020 19:38
-
-
Save accakks/c6747fcb1bef64ab62ddb16f133e7c24 to your computer and use it in GitHub Desktop.
Dynamic solution to max rob amount problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
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