Loot Houses

Posted: 29 Jul, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.

Input Format :
The first line of input contains a single integer 'N' denoting the total number of houses.

The second line of input contains 'N' single space-separated integers, denoting the amount of money in every 'i-th' house.
Output Format :
The only line of output will print the maximum amount of loot that is possible.
Note :
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
0 <= 'N' <= 10^5
0 <= 'A[i]' <= 10^4

Where 'A[i]' represents the money present in the 'i-th' house.

Time limit: 1 sec
Approach 1

Suppose that the robber is at the ith house. The robber has two options:

  • If he decides to rob this house, then he cannot rob the next house, so he’ll have to go to the house after that.
  • If he decides not to rob this house, he has no restriction over choosing the next house.

You will follow the same for the rest of the houses. Thus, if maxLoot(i) is the maximum loot possible when we’re at the ith house, then the recursive definition follows:

maxLoot(i) = maximum( loot[i] + maxLoot(i+2), maxLoot(i+1))

 

Note: This approach has an exponential time complexity because this problem has overlapping subproblems for which we recompute the answer over and over again. To avoid that recomputation, we can store the answer of each recursive call (subproblem) in an array or hashmap so that the next time we need the answer to that subproblem, we can directly fetch it from there instead of calculating it again.

Try Problem