House Robber Problem

You are given a row of houses represented by an array of non-negative integers, where each element is the amount of money in that house. Adjacent houses have a security system that will trigger if two adjacent houses are robbed on the same night. Your task is to determine the maximum amount of money you can rob without triggering the alarm.

The problem can be formulated using dynamic programming. Let \(dp[i]\) be the maximum amount of money that can be robbed from the first \(i+1\) houses. The recurrence relation is \[ dp[i] = \max(\text{houses}[i] + dp[i-2],\ dp[i-1]) \] for \(i \geq 2\), with initial conditions \(dp[0] = \text{houses}[0]\) and \(dp[1] = \max(\text{houses}[0],\text{houses}[1])\). The answer is \(dp[n-1]\) if there are \(n\) houses.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer \(n\) (\(n \geq 0\)), representing the number of houses.
• If \(n > 0\), the second line contains \(n\) space-separated non-negative integers representing the amount of money at each house.

outputFormat

Output a single integer to stdout representing the maximum amount of money that can be robbed without triggering the alarm.

0

0