题解 | #打家劫舍(二)#

#include <bits/stdc++.h>
using namespace std;
int rob_2(vector<int>& nums)
{
	int n = nums.size();
	vector<int>dp(n);
	if (n == 0)
		return 0;
	if (n == 1)
		return nums[0];
	dp[0] = nums[0];
	dp[1] = nums[1];
	for(int i=2;i<n-1;i++)
        dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
    int res = dp[n-2];
    dp[0]=0,dp[1]=nums[1];
    for(int i=2;i<n;i++)
        dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
    res = max(res,dp[n-1]);
	return res;
}
int main()
{
	int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
	int ret = rob_2(arr);
	cout << ret;
	return 0;
}