House Robber Problem

You are a thief trying to maximize the amount of money you can steal from a row of houses. Each house contains a non-negative integer representing the amount of money available, and if two adjacent houses are robbed, the police will be alerted. To avoid this, you cannot rob two consecutive houses.

The problem can be formally defined using dynamic programming. Let \(dp[i]\) denote the maximum amount of money that can be stolen from the first \(i+1\) houses. The recurrence relation is given by:

\(dp[i] = \max(dp[i-1], dp[i-2] + \text{houses}[i])\) for \(i \geq 2\), with the base cases \(dp[0] = \text{houses}[0]\) and \(dp[1] = \max(\text{houses}[0], \text{houses}[1])\).

Your task is to compute \(dp[n-1]\), the maximum amount of money you can steal, given \(n\) houses.

inputFormat

The input is provided via stdin and consists of two lines:

• The first line contains a single integer \(n\), the number of houses.
• The second line contains \(n\) non-negative integers separated by spaces, where the \(i\)-th integer represents the amount of money in the \(i+1\)-th house.

outputFormat

Output to stdout a single integer that represents the maximum amount of money the thief can steal without triggering the alarm system.

4
1 2 3 1

4