content: package question0213_house_robber_ii;
  
  /**
   * 做两次question0198即可。
   *
   * 因为头尾两房子不可以同时偷取，因此我们将其拆解成两步。
   *
   * 第一次只考虑偷取[0, n - 2]的房子，第二次只考虑偷取[1, n - 1]的房子，其中n为nums数组的长度。
   *
   * 时间复杂度是O(n)。空间复杂度是O(1)。
   *
   * 执行用时：1ms，击败97.38%。消耗内存：34.2MB，击败90.00%。
   */
  public class Solution {
      public int rob(int[] nums) {
          int n = nums.length;
          if (n == 0) {
              return 0;
          }
          if (n == 1) {
              return nums[0];
          }
          return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
      }
  
      public int rob(int[] nums, int left, int right) {
          if (left > right) {
              return 0;
          }
          if (left == right) {
              return nums[left];
          }
          int num1 = nums[left], num2 = Math.max(nums[left], nums[left + 1]);
          for (int i = left + 2; i <= right; i++) {
              int tmp = Math.max(num1 + nums[i], num2);
              num1 = num2;
              num2 = tmp;
          }
          return num2;
      }
  }