213. House Robber II.md

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int prev1 = 0;
        int prev2 = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int temp = Math.max(prev1 + nums[i], prev2);
            prev1 = prev2;
            prev2 = temp;
        }
        int max = prev2;
        prev1 = 0;
        prev2 = 0;
        for (int i = nums.length - 1; i >= 1; i--) {
            int temp = Math.max(prev1 + nums[i], prev2);
            prev1 = prev2;
            prev2 = temp;
        }
        return nums.length == 1 ? nums[0] : Math.max(max, prev2);
    }
}

note

• time O(n) space O(1)
• The idea is similar to House Robber 1, but with two passes. There are two situations: rob the first house or rob the last house. So, we will calculate these two cases and return the maximal profit one.