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

Given `[3, 8, 4]`

, return `8`

.

**Challenge**

O(n) time and O(1) memory.

Solution: max[i]表示从0-i个房子里，要抢房子i的最大值

max[i] = Math.max(max[i – 2] + A[i], max[i – 1]);

public long houseRobber(int[] A) { if (A == null || A.length == 0) { return 0; } if (A.length == 1) { return A[0]; } if (A.length == 2) { return Math.max(A[0], A[1]); } //max[i] = for [0-i], the max value if rob house i long[] max = new long[A.length]; max[0] = A[0]; max[1] = A[1]; for (int i = 2; i < A.length; i++) { max[i] = Math.max(max[i - 2] + A[i], max[i - 1]); } return Math.max(max[A.length - 1], max[A.length - 2]); }