> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/dynamic-programming/house-robber.md).

# 1.House Robber

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**.

**Example 1:**

```
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.
```

**Example 2:**

```
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12
```

## Maximum sum such that no two elements are adjacent

### **Algorithm:**

**Maintaining 2 variable :**\
**- max sum including prev element**\
**- max sum excluduing prev element** \
**- maxInc = max(maxInc, maxEnc + current element)**\
**- maxEnc = previous max Inc**

```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        
        if(nums.size()==0){return 0;}
        
        int maxInc = nums[0];
        int maxExc = 0;
        
        for(int i=1;i<nums.size();i++){
            int temp = maxInc;
            maxInc = max(maxExc+nums[i],maxInc);
            maxExc = temp;
        }
        
        return maxInc;
        
    }
};
```

## House Robber II

### All houses at this place are **arranged in a circle. Max adjacent sum in a circular array**

**Approach:**\
**Find Max Adjacent from 0 to n-2 and 1 to n-1.**\
**Return the max of two numbers**

```cpp
class Solution
{
public:
    int maxAdj(vector<int> v, int start, int end)
    {

        int maxInc = v[start];
        int maxExc = 0;

        for (int i = start + 1; i <= end; i++)
        {
            int temp = maxInc;
            maxInc = max(maxInc, maxExc + v[i]);
            maxExc = temp;
        }

        return maxInc;
    }

    int rob(vector<int> &nums)
    {
        if (nums.size() == 1)
        {
            return nums[0];
        }
        return max(maxAdj(nums, 0, nums.size() - 2), maxAdj(nums, 1, nums.size() - 1));
    }
};
```