Leetcode 213: looting II

You are a professional thief , Plan to steal houses along the street , There is a certain amount of cash in every room . All the houses in this place are Make a circle , This means that the first house and the last house are next to each other . meanwhile , Adjacent houses are equipped with interconnected anti-theft system , If two adjacent houses are broken into by thieves on the same night , The system will automatically alarm .

Given an array of non negative integers representing the storage amount of each house , Count you Without triggering the alarm device , The maximum amount you can steal tonight .

Ideas

This topic and 198. raid homes and plunder houses It's almost the same , The only difference is that it's a ring .

For an array , There are three main situations when forming a ring ：

• Situation 1 ： Consider not including leading and trailing elements

 

 

• Situation two ： Consider including the first element , No tail elements

 

• Situation three ： Consider including tail elements , Does not contain the first element

 

Notice that I'm using " consider ", For example, case 3 , Although it is considered to include tail elements , But you don't have to choose the tail element ！ For case three , take nums[1] and nums[3] Is the biggest .

And case two and Situation three It includes case one , So just consider case 2 and case 3 .

So that's the analysis , This question is actually relatively simple .

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        if(len ==2)
            return Math.max(nums[0],nums[1]); 
        return Math.max(robAction(nums, 0, len - 2), robAction(nums, 1, len-1));
    }

    int robAction(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;

        // int[] dp = new int[nums.length];
        // dp[start] = nums[start];
        // dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        // for (int i = start + 2; i <= end; i++) {
        //     dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        // }
        // return dp[end];
    }
}

The first method can save some memory .