题解 | #牛群的夜间保卫II#

#include <algorithm>
#include <vector>
class Solution {
    int subMaxPatrolValue(const vector<int>& values) {
        if(values.size()==1) return values[0];
        if(values.size()==2) return max(values[0], values[1]);
        vector<int>dp(values.size());
        dp[0] = values[0];
        dp[1] = max(values[0], values[1]);
        for(int i=2; i<values.size(); ++i) {
            if(dp[i-1] == dp[i-2]) dp[i] = dp[i-2] + values[i];
            else dp[i] = max(dp[i-1], dp[i-2] + values[i]);
        }
        return dp.back();
    }
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param values int整型vector 
     * @return int整型
     */
    int maxPatrolValue(vector<int>& values) {
        // write code here
        if(values.size()==1) return values[0];
        return max(subMaxPatrolValue(vector<int>(values.begin(), values.end()-1)),
            subMaxPatrolValue(vector<int>(values.begin()+1, values.end())));
    }
};

暂时没想到什么好方法，对比牛群的夜间保卫I，区别无非在于不能同时选择第一个和最后一个牛。