打家劫舍

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

以示例 2 为例：

1. 当只有一个数 2 时我们只能偷2；
2. 当有两个数 2，7 时我们选择偷 7 ；
3. 当有2，7，9 时，我们比较 2+9 和7 谁大就取谁，偷 2+9 =11；
4. 当有2，7，9，3 时我们有 11 和（3+7）比较 选择 11 ；
5. 当2，7，9，3，1 时 11 和 11 +1 我们选择 12。

设 f(n) 为偷盗前 n 个房屋的最高金额，则 f(n) = max( f(n-1), f(n-2) + num)。即偷盗前 n 个房屋可以有偷第 n 个房屋和不偷第 n 个房屋两种选择，取其中金额最大的一个。

public int rob(int[] nums) {
    int preMax = 0, curMax = 0;
    for(int x : nums){
        int temp = curMax;
        curMax = Math.max(preMax + x , curMax);
        preMax = temp;
    }

    return curMax;
}

时间复杂度O(n)，空间复杂度O(1)。