题解 | #不相邻取数#

动态规划：

• 设$dp[i]dp[i]$表示以第$ii$个元素结尾的不相邻元素和的最大值，$dp[i]=Math\mathrm{.}max(dp[i-1],dp[i-2]+nums[i])dp[i]\; =\; Math.max(dp[i-1],dp[i-2]+nums[i])$
• 从所有$dp[i]dp[i]$中找出最大值即是答案

const n = ~~readline()
const arr = readline().split(' ').map(x => ~~x)

function main(arr,n) {
    if(n === 1) return arr[0]
    if(n === 2) return Math.max(arr[0], arr[1])
    let max = 0
    const dp = new Array(n).fill(0)
    dp[0] = arr[0], dp[1] = Math.max(arr[0], arr[1])
    for(let i = 2 ; i < n ; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + arr[i])
        max = Math.max(dp[i], max)
    }
    return max
}

console.log(main(arr,n))