House Robber II

1package pkg5leetcode.blind75;2 3/*4 * House Robber II | LC 2135 * APPROACH: Max of linear rob on [0..n-2] and [1..n-1].6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC213HouseRobberII {9    static int rob(int[] nums) {10        if (nums.length == 1) return nums[0];11        return Math.max(robLinear(nums, 0, nums.length - 2), robLinear(nums, 1, nums.length - 1));12    }13 14    static int robLinear(int[] nums, int lo, int hi) {15        int prev2 = 0, prev1 = 0;16        for (int i = lo; i <= hi; i++) {17            int cur = Math.max(prev1, prev2 + nums[i]);18            prev2 = prev1;19            prev1 = cur;20        }21        return prev1;22    }23 24    public static void main(String[] args) {25        check(rob(new int[]{2, 3, 2}) == 3, "case1");26        check(rob(new int[]{1, 2, 3, 1}) == 4, "case2");27        System.out.println("all tests passed");28    }29 30    static void check(boolean cond, String name) {31        if (!cond) throw new AssertionError("FAILED: " + name);32        System.out.println("  PASS " + name);33    }34}