Last Updated: 30 Oct, 2020
House Robber II
Moderate
Asked in companies
Mr. X is a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden.
All houses along this street are arranged in a circle. That means the first house is the neighbour of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.
You are given an array/list of non-negative integers 'ARR' representing the amount of money of each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.
Note:
It is possible for Mr. X to rob the same amount of money by looting two different sets of houses. Just print the maximum possible robbed amount, irrespective of sets of houses robbed.
For example:
(i) Given the input array arr[] = {2, 3, 2} the output will be 3 because Mr X cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. So, he’ll rob only house 2 (money = 3)
(ii) Given the input array arr[] = {1, 2, 3, 1} the output will be 4 because Mr X rob house 1 (money = 1) and then rob house 3 (money = 3).
(iii) Given the input array arr[] = {0} the output will be 0 because Mr. X has got nothing to rob.
Input Format :
The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.
The first line of each test case contains an integer, ‘N’ representing the size of the first array/list.
The second line of each test case contains 'N' single space-separated integers representing the array/list elements.
Output Format :
For each test case, print a single line containing a single integer denoting the maximum money that can be robbed in a separate line.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 5 x 10 ^ 3
1 <= ARR[i] <= 10 ^ 9
Time limit: 1 sec.
Approaches
The main point is that you can't rob both the first and the last houses.
Therefore, the core idea is to apply dynamic programming. Two cases are considered here:
- When you rob the first house
- When you don't rob the first house, i.e. you rob the last one.
The dynamic programming algorithm that must be applied considering two arrays, given array ARR and new array DP to store value till the ith house is:
- Initialize DP[0] to 0 and DP[1] = ARR[1]
- Iterate over houses
- At the ith house you have two options:
- Keep the money from the (i-1)th (previous) house, skipping the ith house, i.e. DP[i-1]
- Rob the ith house after the (i-2)th house, skipping the (i-1)th i.e. DP[i-2]+ARR[i]
- Choose the most profitable option i.e. Maximum of DP[i-1] and DP[i-2] + ARR[i]
- Return the sum you've got after the last house
Similar problems