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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param values int整型一维数组
 * @return int整型
 */

/**
 * 我们有两种选择：
        - 盗取第 i 个牛，那么前 i 个牛的最大价值为前 i-2 个牛的最大价值加上第 i 个牛的价值。
        - 不盗取第 i 个牛，那么前 i 个牛的最大价值为前 i-1 个牛的最大价值。
        
    转移方程：dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1])
 */

export function maxPatrolValue(values: number[]): number {
    // write code here
    const n = values.length;
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return values[0];
    }
    const dp = new Array(n);
    dp[0] = values[0];
    dp[1] = Math.max(values[0], values[1]);

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

    return dp[n - 1];
}