package com.fishercoder.solutions;
/**213. House Robber II

 Note: This is an extension of House Robber.

After robbing those houses on that street,
 the thief has found himself a new place for his thievery
 so that he will not get too much attention.
 This time, all houses at this place are arranged in a circle.
 That means the first house is the neighbor of the last one.
 Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.
*/
public class _213 {

    /**Another dp problem:
     * separate them into two cases:
     * 1. rob from house 1 to n-1, get max1
     * 2. rob from house 2 to n, get max2
     * take the max from the above two max*/
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int[] dp = new int[nums.length - 1];

        //rob 1 to n-1
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length - 1; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        int prevMax = dp[nums.length - 2];

        //rob 2 to n
        dp = new int[nums.length - 1];
        dp[0] = nums[1];
        dp[1] = Math.max(nums[1], nums[2]);
        for (int i = 3; i < nums.length; i++) {
            dp[i - 1] = Math.max(dp[i - 3] + nums[i], dp[i - 2]);
        }
        return Math.max(prevMax, dp[nums.length - 2]);
    }

}

@@ -31,16 +31,20 @@
 ons;%0A/**
+%0A * 
 213. Hou
@@ -103,16 +103,17 @@
 obber.%0A%0A
+ 
 After ro
@@ -562,16 +562,17 @@
 h house,
+%0A
  determi
@@ -678,16 +678,67 @@
 3 %7B%0A
-%0A    /**
+    public static class Solution1 %7B%0A        /**%0A         * 
 Anot
@@ -758,16 +758,20 @@
 m:%0A     
+   
+ 
 * separa
@@ -794,16 +794,20 @@
  cases:%0A
+    
      * 1
@@ -847,16 +847,20 @@
 x1%0A     
+ 
+   
 * 2. rob
@@ -891,15 +891,8 @@
 max2
-%0A     *
  tak
@@ -923,19 +923,33 @@
  two max
-*/%0A
+%0A         */%0A    
     publ
@@ -973,32 +973,36 @@
 nums) %7B%0A        
+    
 if (nums == null
@@ -1033,24 +1033,28 @@
             
+    
 return 0;%0A  
@@ -1051,16 +1051,20 @@
 turn 0;%0A
+    
         
@@ -1065,32 +1065,36 @@
       %7D%0A        
+    
 if (nums.length 
@@ -1109,24 +1109,28 @@
             
+   
+ 
 return nums%5B
@@ -1133,32 +1133,36 @@
 ums%5B0%5D;%0A        
+    
 %7D%0A        if (nu
@@ -1147,32 +1147,36 @@
       %7D%0A        
+ 
+   
 if (nums.length 
@@ -1179,24 +1179,28 @@
 gth == 2) %7B%0A
+    
             
@@ -1234,32 +1234,36 @@
 ms%5B1%5D);%0A        
+    
 %7D%0A        int%5B%5D 
@@ -1256,16 +1256,20 @@
         
+ 
+   
 int%5B%5D dp
@@ -1302,24 +1302,28 @@
 %5D;%0A%0A        
+   
+ 
 //rob 1 to n
@@ -1325,16 +1325,20 @@
  to n-1%0A
+    
         
@@ -1354,32 +1354,36 @@
 ums%5B0%5D;%0A        
+ 
+   
 dp%5B1%5D = Math.max
@@ -1402,32 +1402,36 @@
 ms%5B1%5D);%0A        
+   
+ 
 for (int i = 2; 
@@ -1450,32 +1450,36 @@
 gth - 1; i++) %7B%0A
+    
             dp%5Bi
@@ -1524,34 +1524,42 @@
  - 1%5D);%0A        
+ 
-%7D%0A
+   %7D%0A    
         int prev
@@ -1590,24 +1590,28 @@
 %5D;%0A%0A        
+    
 //rob 2 to n
@@ -1619,16 +1619,20 @@
         
+ 
+   
 dp = new
@@ -1654,32 +1654,36 @@
 h - 1%5D;%0A        
+   
+ 
 dp%5B0%5D = nums%5B1%5D;
@@ -1679,24 +1679,28 @@
  = nums%5B1%5D;%0A
+    
         dp%5B1
@@ -1731,32 +1731,36 @@
 ms%5B2%5D);%0A        
+ 
+   
 for (int i = 3; 
@@ -1775,32 +1775,36 @@
 .length; i++) %7B%0A
+    
             dp%5Bi
@@ -1853,32 +1853,36 @@
  - 2%5D);%0A        
+    
 %7D%0A        return
@@ -1867,32 +1867,36 @@
       %7D%0A        
+ 
+   
 return Math.max(
@@ -1930,13 +1930,22 @@
 %5D);%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 213