题解 | #不相邻取数#

不相邻取数

http://www.nowcoder.com/practice/a2be806a0e5747a088670f5dc62cfa1e

动态规划:

  • dp[i]dp[i]表示以第ii个元素结尾的不相邻元素和的最大值,dp[i]=Math.max(dp[i1],dp[i2]+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))
全部评论

相关推荐

头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务