/*
 * @lc app=leetcode.cn id=213 lang=cpp
 *
 * [213] 打家劫舍 II
 */

// @lc code=start
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        
        int a = rob1(nums, 0, n - 2);
        int b = rob1(nums, 1, n - 1);
        return max(a, b);
    }

    int rob1(vector<int>& nums, int l, int r) {
        vector<int> dp(2);
        int n = r - l + 1;
        dp[1] = nums[l];
        for (int i = l + 1; i < r + 1; ++i) {
            int tmp = dp[0];
            dp[0] = max(dp[0], dp[1]);
            dp[1] = tmp + nums[i];
        }
        return max(dp[0], dp[1]);
    }
};
// @lc code=end