House robber

A robber wants to steal money from n houses built in a line, each of which contains some money in it. Given he can’t steal from two adjacent houses, find the maximum amount of money can be steal.

Hint

To understand how this algorithm works, imagine we're moving through the houses from the very end. At each house, the robber faces a simple choice:

Rob this house: If they rob this house, they cannot rob the previous house due to the security system.
Skip this house: If they skip this house, they can potentially rob the previous house.

The robber will always choose the option that maximizes the amount they can steal at that point. By making this decision at each house and working our way backwards, we effectively solve the problem. Essentially, we're breaking down the larger problem of robbing the entire street into smaller, more manageable subproblems.

Python
Javascript

# Python implementation

def rob(ls):
  if len(ls) <= 0:
    return 0

  return max(ls[-1] + rob(ls[:-2]), rob(ls[:-1]))

ls = [6, 7, 1, 3, 8, 2, 4]

print(rob(ls))

// Javascript implementation

function rob(list) {
  if (list.length <= 0) {
    return 0;
  }

  return Math.max(list[list.length - 1] + rob(list.slice(0, -2)), rob(list.slice(0, -1)));
}

const list = [6, 7, 1, 3, 8, 2, 4];

console.log(rob(list));