Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

You are a professional thief who plans to rob the houses along the street, each of which contains a certain amount of cash. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with an interconnected security system, if two adjacent houses are broken into on the same night, the system will automatically alarm. Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal tonight without setting off the alarm.

Answer:

198. What is the meaning of the passage? And we’re going to expand down from this problem.

The first house and the last house are connected. According to the rules, two neighboring houses cannot be stolen. Therefore, only one house can be stolen from the first house and the last house.

In the last problem, we used dynamic programming, and we can do that again. To use a dynamic programming approach similar to the previous one, we need to have an initial state, so for the moment we can think of it as an array of houses with heads and tails, rather than a ring, but consider it in two different ways:

  1. Steal the first house, not the last.
  2. Steal the last house, not the first.

Suppose there are n houses in total and the advanced contained in the houses are stored in the array NUMs [n], then the array ranges corresponding to the two cases are:

  1. The subscript from0 到 n - 2Subarray of.
  2. The subscript from1 到 n - 1Subarray of.

Then, the above two word groups were respectively used in the method to find the results, and then take two results of the larger one, is the final result of the problem.

Final code:

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }
    public int robRange(int[] nums, int start, int end) {
        int y = 0, n = 0;
        for (int i = start; i <= end; i++) {
            int num = nums[i];
            int temp = n + num;
            n = Math.max(y, n);
            y = temp;
        }
        returnMath.max(y, n); }}Copy the code