You are a professional robber, and after weeks of planning, you plan to rob some houses along a street. Each of these houses has a lot of money and valuables. Let’s say that you cannot rob houses adjacent to each other since they have security and burglar alarms installed.

Following the above-mentioned constraint and given an integer array, money, that represents the amount of money in each house, return the maximum amount of money you can steal tonight without alerting the police.

Let’s say you have an array of money as follows:

  • money: [1, 2, 3, 4, 5]

Considering we cannot rob the adjacent houses, we have six possible combinations that can possibly yield a substantial amount. Out of these combinations, we'll find one that yields the maximum money. The possible combinations are as under:

  • 1+3+5=91+3 +5 = 9

  • 1+4=51+4 = 5

  • 1+5=61+5 = 6

  • 2+4=62+4 = 6

  • 2+5=72+5 = 7

  • 3+5=83+5 = 8

Though all of the combinations described above are valid, we need to select the one with the maximum theft value. Hence, we will rob house 1, house 3, and house 5 as they give us the maximum theft amount of 9.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.