题意理解

同样的，也是从一个数组中不相邻地取出若干的数，使其之和最大，这里把第0个数和最后一个数视为相邻的。

方法一

动态规划
和题目176一样，我们使用value数组表示从前往后到第i个数字，且选择第i个数字的时候，选到的数之和的最大值。因为最后的结果中肯定有某个数是最后一个被选到的数字，所以我们只要遍历一遍value，找到其最大值即可。

不同的是，由于第0个数和最后一个数相邻，我们要分两种情况讨论，一是选第0个数，不选最后一个数；另一种是正好相反。最后比较这两种情况下的最大值谁更大。

至于value[i]怎么求。我们假设已经知道之前每个位置上的value，value[i]则为nums[i]加上value[0]~value[i-2]之间的最大值，nums[i-1]是不能被选的。这样状态转移方程就很简单，且考虑了所有情况。

以[2,4,5,8,3]为例，示意图如下：

同样的，为了避免双重循环，使用maxm记录value[i]之前的最大值。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        vector<int> value;
        //处理偷第1家的情况
        for (int i=0;i<nums.size();i++)
        {
            value.push_back(nums[i]);
        }
        int ans = max(value[0],value[1]);
        //用一个maxm记录value[i-1]之前的最大值。
        int maxm = value[0];
        for (int i=2;i<nums.size()-1;i++)
        {
            //更新maxm的值
            if ((i-2)>0) maxm = max(maxm, value[i-2]);
            value[i] += maxm;
            ans = max(ans, value[i]);
        }
        //处理不偷第1家的情况
        value.clear();
        for (int i=0;i<nums.size();i++)
        {
            value.push_back(nums[i]);
        }
        //用一个maxm记录value[i-1]之前的最大值。
        maxm = value[1];
        //i从3开始
        for (int i=3;i<nums.size();i++)
        {
            //更新maxm的值
            if ((i-2)>0) maxm = max(maxm, value[i-2]);
            value[i] += maxm;
            ans = max(ans, value[i]);
        }
        return ans;
    }
};

时间复杂度：$O(N)O(N)$。只对nums和value数组分别进行了两次遍历，长度均为N。
空间复杂度：$O(N)O(N)$。开辟了新数组value，长度和nums一样都为N。

方法二

动态规划
这次换一种思路。既然每个数字有2种情况，选或者不选，那么就使用一个二维数组dp，其行数为nums的大小，有2列（0表示不选，1表示选）。状态转移方程为：

$dp[i][0]=max(dp[i-1][0],dp[i-1][1])dp[i][0]\; =\; max(dp[i-1][0],dp[i-1][1])$
$dp[i][1]=dp[i-1][0]+nums[i]dp[i][1]\; =\; dp[i-1][0]\; +\; nums[i]$

这里要注意分类讨论。
偷第0家时，$dp[0][1]=nums[0];dp[nums\mathrm{.}size()-1][1]=0dp[0][1]\; =\; nums[0];\; dp[nums.size()-1][1]\; =\; 0$。
偷最后一家时，$dp[0][1]=0dp[0][1]\; =\; 0$。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        //偷第0家
        vector<vector<int>> dp = vector<vector<int>>(nums.size(),vector<int>(2,0));
        dp[0][1] = nums[0];
        for (int i=1;i<nums.size();i++)
        {
            dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
            if (i!=nums.size()-1) dp[i][1] = dp[i-1][0] + nums[i];
        }
        int ans = dp[nums.size()-1][0];
        //不偷第0家
        dp = vector<vector<int>>(nums.size(),vector<int>(2,0));
        for (int i=1;i<nums.size();i++)
        {
            dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        //返回时在要在是否选择最后一个数中判断一下
        return max(ans,max(dp[nums.size()-1][0],dp[nums.size()-1][1]));
    }
};

时间复杂度：$O(N)O(N)$。只对nums数组进行了两次遍历，其长度为N。
空间复杂度：$O(N)O(N)$。开辟了新的二维数组dp，列数是固定值为2。