不添加 2 个连续值的数组中的最大总和

Question

我正在应对来自 codefights.com 的挑战。
给定一个整数数组（可能为负数），我需要 return 在不相加两个连续整数的情况下可以达到的最大总和（我不能更改数组的顺序）。

不容易解释，所以这里有几个例子：

输入：[1, 2, 3, 4]：你要通过'1'，取2，不能取3，取4，你得6。
输入：[1, 3, 1]: 传递'1'，取3，你不能取1，所以你有3.

虽然我用这段代码得到了它：

function solve(vals) {
  var even=0; var odd=0;
  for(var i=0; i<vals.length; i++){
    if(i%2==0){
      even+=vals[i];
    } else {
      odd+=vals[i];
    }
  }
  return Math.max(even, odd);
}

但后来我得到了这个测试用例：[1,0,0,3] 它应该 return 4，跳过两个 '0' 这让我意识到我一直在看错了.
现在我卡住了，真的不知道该怎么做。

有什么想法吗？

编辑：

根据 MrGreen 的回答，我得到了这个：

function target_game(a) {
    var dp=[], l=a.length-1;
    dp[0]=a[0];
    dp[1]=Math.max(a[0],a[1]);

    for(var i=2; i<=a.length-1; i++){
        dp[i]=Math.max(dp[i - 1], dp[i - 2] + a[i]);
    }

    return dp[l];
}

除非数组包含负值，否则它工作正常。
此输入：[-1,0,1,-1] returns 0。我仍在努力解决问题，但我正在编辑问题以获得防弹解决方案：p

Answer 1

这是一个经典的动态规划问题。

定义dp[i]为考虑0到i的元素所能得到的最大和。

然后dp[i] = max(dp[i - 1], dp[i - 2] + a[i])

这背后的直觉，如果你在总和中取a[i]那么你就不能取a[i - 1]

基本案例：dp[0] = max(0, a[0]) 和 dp[1] = max(0, a[0], a[1])

你可以看看这节课：

part-1 part-2 part-3 part-4

Answer 2

这是挑战的 "best" 答案（实际上最短）：

function solve(a) {
  b = t = 0
  for (i in a) {
    c = b + a[i]
    b = t
    t = c > t ? c : t
  }
  return t
}

这是我重命名变量以使其更易于理解的版本：

function solve(vals) {
  prevTotal = total = 0
  for (i in vals) {
    alt = prevTotal + vals[i]
    prevTotal = total
    total = alt > total ? alt : total
  }
  return total
}

不添加 2 个连续值的数组中的最大总和

Biggest sum from array without adding 2 consecutive value

javascript

arrays

challenge-response