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 system 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.
You can find and test your solution on Leetcode: house robber.
For example, if we consider the following array: [10 13 23 17 6 11 18 16] representing the amount of money of each house
along the street then the robber can earn 60$ without being detected.
Indeed, if the robber steals the house 0 (10$), the house 2 (23$), the house 5 (11$) and the house 7 (16$), it repesents
60$ in total and no robbed houses are stolen.
Reasonning step
Let consider the previous example and see the reasonning to get the maximum amount of money of 60 $.
The idea is to avoid that two adjacents houses are stolen. To do that we will consider two types of houses:
the houses with an odd index and the house with an even index.
For each type of house, we assign a current profit. Let call odd_profit the profit for odd houses and
even_profit the profit for even houses.
If at a given house, we notice that the profit of the other type of house is greater then we assign this higher
profit. Here are the steps with the previous example:
The final odd_profit is greater than the final even_profit, we return the odd_profit. You can
check that two adjacent houses are not stolen during the night.
As usual, here is the source code:
int rob(vector<int> &num) {
int even_profit = 0;
int odd_profit = 0;
for(int i = 0; i < num.size(); i++)
{
if(i%2)
{
even_profit += num[i];
even_profit = (even_profit>odd_profit?even_profit:odd_profit);
}
else
{
odd_profit += num[i];
odd_profit = (odd_profit>even_profit?odd_profit:even_profit);
}
}
return (even_profit>odd_profit?even_profit:odd_profit);
}