## Problem Statement

In this problem there are houses in a street and House robber has to rob these houses. But the problem is that he can’t rob more than one house successively i.e which are adjacent to each other. Given a list of non-negative integers representing the amount of money of each house, we have to find out the maximum amount of money he can get.

### Example

nums = [1,2,3,1]

4

Explanation:

Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

nums = [2,7,9,3,1]

12

Explanation:

Rob house 1 (money = 2), rob house 3 (money = 9) and then 5th (money = 1).

Total amount you can rob = 2 + 9 + 1 = 12.

## Approach

This problem can not be solved by greedy approach.

Let us take an example:

nums = [1,7,9,5,1,3,4]

If we would go for max element in the array(ie. 9), we would loose its adjacent sum (ie. 7+5). And best we can have is 15 as total sum.

If we go for even or odd position elements we have even sum=15 (7+5+3) and odd sum=15(1+9+1+4).

The optimum answer for this example will be [7+5+4]=12.

Hence to solve this type of problem we have to search for all choices recursively and pick out the maximum from them. Let us denote that:

f(n) = Largest amount that you can rob from first house to nth indexed house.

Ai = Amount of money at the ith index house.

At each house we have the choice of robbing it or leaving it.

case 1 – if we pick last house:

then, we cant pick (n-1)th house, hence f(n)= An + f(n-2)

case 2 – if we leave last house:

then, we will stick with the max profit till (n-1)th house, hence f(n)= f(n-1)

Let us see base cases.

n = 0, clearly f(0) = A0.

n = 1, then f(1) = max(A0, A1).

Hence we can summarize the formula as following :

f(n)= max( An + f(n-2) , f(n-1) )

This is a recursive formula which we can implement through simple recursion but here the time complexity will be O(2^n). Therefore we will use dynamic programming approach and store the intermediate results in an array.

After calculating we will return the value stored at nth(last) index in array.

## Implementation

### C++ Program for House Robber Leetcode Solution

#include <bits/stdc++.h> using namespace std; int rob(vector<int>& nums) { int n=nums.size(); if(n==0) return 0; if(n==1) return nums[0]; int a[n]; a[0]=nums[0]; a[1]=max(nums[0],nums[1]); for(int i=2;i<n;i++) a[i]=max(nums[i]+a[i-2], a[i-1]); return a[n-1]; } int main() { vector<int> arr={1,2,3,1}; cout<<rob(arr)<<endl; return 0; }

4

### Java Program for House Robber Leetcode Solution

import java.util.*; import java.lang.*; class HouseRobber { public static int rob(int[] nums) { int n=nums.length; if(n==0) return 0; if(n==1) return nums[0]; int a[]=new int[n]; a[0]=nums[0]; a[1]=Math.max(nums[0],nums[1]); for(int i=2;i<n;i++) a[i]=Math.max(nums[i]+a[i-2], a[i-1]); return a[n-1]; } public static void main(String args[]) { int arr[]={1,2,3,1}; System.out.println(rob(arr)); } }

4

## Complexity Analysis for House Robber Leetcode Solution

**Time Complexity**

**O(n) : **we are iterating from 1st house to nth house in a single loop, where n is the number of total houses.

**Space Complexity **

**O(n) : **we have used an array of size n to store the intermediate result.