@@ -0,0 +1,2562 @@
+import org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0A/**%0A * You are a professional robber planning to rob houses along a street. Each house has a certain amount of money%0A * stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system%0A * connected and it will automatically contact the police if two adjacent houses were broken into on the same night.%0A * %3Cp%3E%0A * Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount%0A * of money you can rob tonight without alerting the police.%0A * %3Cp%3E%0A * Tags: Dynamic Programming%0A * %3Cp%3E%0A * Similar Problems: (M) Maximum Product Subarray (M) House Robber II (M) Paint House (E) Paint Fence (M) House%0A * Robber III%0A */%0Apublic class HouseRobber %7B%0A%0A    private HouseRobber hr;%0A%0A    /**%0A     * Recurrence relation: max%5Bn%5D = max(max%5Bn - 2%5D + nums%5Bn%5D, max%5Bn - 1%5D)%0A     * Optimization: use constant variables instead of an array%0A     */%0A    public int rob(int%5B%5D nums) %7B%0A        if (nums == null %7C%7C nums.length == 0) return 0;%0A        if (nums.length == 1) return nums%5B0%5D;%0A        int preMax = nums%5B0%5D;%0A        int max = Math.max(nums%5B0%5D, nums%5B1%5D);%0A        for (int i = 2; i %3C nums.length; i++) %7B%0A            int temp = preMax;%0A            preMax = max;%0A            max = Math.max(temp + nums%5Bi%5D, preMax);%0A        %7D%0A        return max;%0A    %7D%0A%0A    @Before%0A    public void setUp() %7B%0A        hr = new HouseRobber();%0A    %7D%0A%0A    @Test%0A    public void testInvalidInput() %7B%0A        Assert.assertEquals(0, hr.rob(null));%0A    %7D%0A%0A    @Test%0A    public void testEdgeCases() %7B%0A        int%5B%5D input = %7B%7D;%0A        Assert.assertEquals(0, hr.rob(input));%0A        input = new int%5B%5D%7B1%7D;%0A        Assert.assertEquals(1, hr.rob(input));%0A        // 10 -%3E 10%0A        input = new int%5B%5D%7B10%7D;%0A        Assert.assertEquals(10, hr.rob(input));%0A        // 1, 2 -%3E 2%0A        input = new int%5B%5D%7B1, 2%7D;%0A        Assert.assertEquals(2, hr.rob(input));%0A        // 2, 1 -%3E 2%0A        input = new int%5B%5D%7B2, 1%7D;%0A        Assert.assertEquals(2, hr.rob(input));%0A    %7D%0A%0A    @Test%0A    public void testWithExamples() %7B%0A        // 1, 2, 3 -%3E 4%0A        int%5B%5D input = %7B1, 2, 3%7D;%0A        Assert.assertEquals(4, hr.rob(input));%0A        // 1, 2, 3, 4 -%3E 6%0A        input = new int%5B%5D%7B1, 2, 3, 4%7D;%0A        Assert.assertEquals(6, hr.rob(input));%0A        // 2, 8, 3, 6, 5 -%3E 14%0A        input = new int%5B%5D%7B2, 8, 3, 6, 5%7D;%0A        Assert.assertEquals(14, hr.rob(input));%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        hr = null;%0A    %7D%0A%7D%0A

add house robber