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

import java.util.*;

//建议分成两块求解 带尾巴和不带尾巴 转换成牛群夜间保卫1的dp方式
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param values int整型一维数组 
     * @return int整型
     */
    public int maxPatrolValue (int[] values) {
        int n=values.length;
        int[] dp=new int[n];
        int[] dp1=new int[n];
        dp[0]=0;
        dp[1]=values[0];
        dp[2]=Math.max(dp[1],dp[0]+values[1]);
        for(int i=3;i<n;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+values[i-1]);
        }
        dp1[0]=0;dp1[1]=values[1];

           for(int i=2;i<n;i++){
            dp1[i]=Math.max(dp1[i-1],dp1[i-2]+values[i]);
        }

        return Math.max(dp[n-1],dp1[n-1]);
    }
}