ruby - 理解 leetCode - 121. 买卖股票的最佳时机 - Ruby

Question

我试图了解我为以下 leetCode 问题找到的解决方案。
描述:
“您将获得一系列价格，其中价格 [i] 是给定股票在第 i 天的价格。
您希望通过选择某一天购买一只股票并选择 future 的另一天出售该股票来最大化您的利润。
返回您可以从这次交易中获得的最大利润。如果您无法获得任何利润，则返回 0。”
解释:
"输入:价格 = [7,1,5,3,6,4]
输出:5
解释:在第 2 天买入(价格 = 1)并在第 5 天卖出(价格 = 6)，利润 = 6-1 = 5。
请注意，不允许在第 2 天买入并在第 1 天卖出，因为您必须先买入再卖出。”
我遇到了我试图理解的这个解决方案。在“->”处分解:

def max_profit([7,1,5,3,6,4])
  value = 0
  profit = 0

  (1...prices.size).each do |i|
    value += (prices[i] - prices[i-1])

-> 所以这里 value = 0 + (1-7 = -6)= -6/value = -6 + (5-1=4)= -2/value = -2+(3-5)=-4 和以-3结尾

    value = [0, value].max

-> 这是我不明白的。现在 value = [0, value].max 并且当我打印它时我得到 0,4,2,5,3。
我看到这个的方式是:
(在第一次迭代中) value = [0, -6].max, 所以 value 是 0 因为 0 > than -6
但是当 value = [0, -2].max 时，第二次迭代我得到 4 ......它不应该再次为 0 吗？？怎么得到 0,4,2,5,3 ???
当我执行 value = [0, value].max 时实际发生了什么。 ?

profit = value if value > profit
  end

  profit
end

一百万谢谢

Answer 1

理解程序的一个好方法是简单地用笔和纸逐步完成它，同时跟踪所有(相关)状态。所以，让我们这样做。
在我们的例子中，相关状态是两个局部变量 profit 的值。和 value以及迭代变量i并通过扩展 prices[i]和 prices[i-1] .我们首先将它们都初始化为值 0在方法的第 1 行和第 2 行中。然后，第 4-8 行是执行所有实际工作的循环；第 10 行简单地返回结果。很容易看出第 5-7 行是做所有工作的，所以让我们关注那些:

i线
代码
它有什么作用？profitvalueprices[i]prices[i-1]
15value += (prices[i] - prices[i-1])将价格差异添加到当前值00 -6 = -67116value = [0, value].max套装value最大 0及其当前值，IOW 集 value至 0如果是阴性007117profit = value if value > profit套装profit到其当前值的最大值和 value007125value += (prices[i] - prices[i-1])将价格差异添加到当前值00 + 4 = 41526value = [0, value].max套装value最大 0及其当前值，IOW 集 value至 0如果是阴性041527profit = value if value > profit套装profit到其当前值的最大值和 value441535value += (prices[i] - prices[i-1])将价格差异添加到当前值44 - 2 = 25336value = [0, value].max套装value最大 0及其当前值，IOW 集 value至 0如果是阴性425337profit = value if value > profit套装profit到其当前值的最大值和 value445345value += (prices[i] - prices[i-1])将价格差异添加到当前值42 + 3 = 53646value = [0, value].max套装value最大 0及其当前值，IOW 集 value至 0如果是阴性453647profit = value if value > profit套装profit到其当前值的最大值和 value553655value += (prices[i] - prices[i-1])将价格差异添加到当前值55 - 2 = 36456value = [0, value].max套装value最大 0及其当前值，IOW 集 value至 0如果是阴性536457profit = value if value > profit套装profit到其当前值的最大值和 value5364

What actually happens when I do value = [0, value].max. ?

了解方法作用的最简单方法是阅读 its documentation [注意，从技术上讲，这种方法不是 Enumerable#max但是 Array#max ，但在本例中它们的行为相同]:

Returns the object in enum with the maximum value.

因此，换句话说，该方法正如其名称所暗示的那样:它返回 Enumerable 的最大值。 .
请注意，这不是编写代码的非常惯用的方式。例如，使用 max 没有意义。在第 6 行和 if在第 7 行做同样的事情:坚持一个或另一个，不要用两种不同的东西做同样的事情来混淆读者。此外，在 Ruby 中几乎从未对集合进行手动迭代。使用 Enumerable#each_cons 可以更好地表达这一点。和例如 Enumerable#max_by 或 Enumerable#reduce .实际上，完美的解决方案是使用 prefix sum aka scan ，但不幸的是，这在 Ruby 的核心和标准库中是不可用的。
惯用的版本看起来更像这样:

def max_profit(prices)
  prices.
    each_cons(2).
    reduce([0, 0]) do |(value, profit), (a, b)|
      [[temp = value + b - a, 0].max, [temp, profit].max] 
    do.
    last
end

或这个:

def max_profit(prices)
  prices.
    each_cons(2).
    map {|a, b| b - a }.
    reduce([]) do |res, difference|
      res << [(res[-1] || 0) + difference, 0].max
    end.
    max
end