2

我正在处理来自 codefights.com 的挑战。
给定一个整数数组（可能是负数），我需要返回在不添加两个连续整数的情况下可以达到的最大总和（我无法更改数组的顺序）。

不容易解释，这里举几个例子：

  • 输入：[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] 它应该返回 4，跳过了两个“0”，这让我意识到我一直在看错。
现在我被卡住了，真的不知道该怎么做。

有任何想法吗 ？

编辑：

使用格林先生的回答，我得到了这个：

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] 返回 0。我仍在努力修复，但我正在编辑问题以获得防弹解决方案：p

4

2 回答 2

4

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

定义为如果我们考虑从到dp[i]的元素，我们可以获得的最大总和。0i

然后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])

你可以看看这节课：

第 1 部分 第 2 部分 第 3 部分 第 4 部分

于 2015-07-23T09:11:21.343 回答
0

这是挑战的“最佳”答案（实际上是最短的）：

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
}
于 2015-07-24T07:41:47.913 回答