You are planning to rob houses on a specific street, and you know that every hou

Question

You are planning to rob houses on a specific street, and you know that every house on the street has a certain amount of money hidden. The only thing stopping you from robbing all of them in one night is that adjacent houses on the street have a connected security system. The system will automatically trigger an alarm if two adjacent houses are broken into on the same night. Given a list of non-negative integers nums representing the amount of money hidden in each house, determine the maximum amount of money you can rob in one night without triggering an alarm.

Explanation / Answer

#if a house is robbed, then house next to it cant be robbed
#it is dynamic programming, to find max of amount that can be robbed
# find max of two amounts,
#first : if ith house is robbed, amount[i] + max of amount that can be robbed from i+2 to last house
#second : if ith account is not robbed, i+1 house can be robed, thus the max amount that can be robbed from i+1 th house to last house

#findMax is the function to find max amount tht can be robbed
def findMax(arr,i):
   if(i==len(arr)-1):
       return arr[i]
   if(i==len(arr)-2):
   return max(arr[i],arr[i+1])
   return max(arr[i]+findMax(arr,i+2),findMax(arr,i+1))

# n : Number of houses
#arr : array of amount in each house (all positive)

n = int(input('Enter number of houses'))
arr=[0]*n
for i in range(n):
   print( 'house ', i+1,)
   arr[i] = int(input('Enter money in the house : '))

print('Max amount of that can be robbed :',findMax(arr,0))

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.