arrays - Ruby - 数组中非相邻整数的最大数组总和

Question

此代码遍历数组并返回非相邻整数的最大总和。这是来自 HackerRank - 谁能解释为什么这有效？这是我在网上找到的解决方案，但我不明白，也没有自己弄明白。

谢谢!

https://www.hackerrank.com/challenges/max-array-sum/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dynamic-programming

def maxSubsetSum(arr)
    incl = 0
    excl = 0
    temp = 0
    for i in 0...arr.size
        temp = incl
        incl = [arr[i]+excl, temp].max            
        excl = temp
    end
return [incl, excl].max
end

maxSubsetSum([1,3,5,2,4,6,8])

Answer 1

这是一些非常丑陋(丑陋我的意思是不合逻辑)的 Ruby 代码，所以让我们在继续之前清理它:

def maxSubsetSum(arr)
  incl = 0
  excl = 0
  temp = 0
  arr.each do |value|
    temp = incl
    incl = [value + excl, temp].max            
    excl = temp
  end
  [incl, excl].max
end

maxSubsetSum([1,3,5,2,4,6,8])

现在我们可以开始分析这段代码了。我已经遍历并在循环的每一步写入了每个变量的值:

value = 1
temp = 0
incl = 1
excl = 0

value = 3
temp = 1
incl = 3
excl = 1

value = 5
temp = 3
incl = 6
excl = 3

value = 2
temp = 6
incl = 6
excl = 6

value = 4
temp = 6
incl = 10
excl = 6

value = 6
temp = 10
incl = 12
excl = 10

value = 8
temp = 12
incl = 18
excl = 12

(return 18)

在任何给定点，程序都在确定它是否应该“使用”一个值——使用一个值的缺点是您不能使用它后面的值，因为它是相邻的。在该过程的每一步，它都会将当前值添加到 excl(表示上一步的最佳总和，不包括该值)与 incl(技术上 temp 但 temp 在该阶段持有 incl )，它表示包含值的前一次迭代的值。

temp 不会跨循环被记住；在循环的每次迭代之后，唯一重要的值是 incl 和 excl。重申一下，在每个循环结束时，incl 保存包含前一个数字的最佳和，excl 保存不包含前一个数字的最佳和。在循环的每一步，都会重新计算 incl 和 excl 以反射(reflect)新值的包含或排除。

为了证明这个过程确实有效，让我们考虑上面的数组，但在末尾有一个额外的元素 7。所以现在我们的数组看起来像这样:[1,3,5,2,4,6 ,8,7]。我们已经完成了之前列表中的大部分工作。我们设置temp为18，incl变为[7 + 12, 18].max也就是 19，excl 变为 18。现在我们可以看到，包括最后这个数字意味着我们得到一个比之前的结果更大的数字，所以我们必须使用它，这意味着我们不能使用我们以前使用的8得到我们的结果。

此过程称为动态规划，为了确定整个问题的答案，您将问题分解并增加其复杂性。在这种情况下，我们将数组分解，然后慢慢地添加回每个值，跟踪前一部分的最佳结果是什么。