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

Question

我正在尝试理解我为以下leetCode问题找到的解决方案。

描述： "你会得到一系列价格，其中价格[i]是给定股票在第i天的价格。 您希望通过选择一天购买一只股票并选择未来不同日期出售该股票来最大化您的利润。 返还您可以从此交易中获得的最大利润。如果您无法实现任何利润，则返回 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])

->

所以这里的值 = 0 + (1-7 = -6)= -6/值 = -6 + (5-1=4)= -2/值 = -2+(3-5)=-4 以此类推，以 -3 结尾

value = [0, value].max

->这是我没有得到的。现在值 = [0， 值].max当我打印它时，我得到 0,4,2,5,3。

我看到这个的方式是： (在第一次迭代中)值 = [0， -6].max，因此值为 0，因为 0 比 -6>

但是当值 = [0， -2]时，我第二次迭代得到 4.max ...不应该又是0吗？？我如何得到0,4,2,5,3???

当我做值 = [0， 值].max 时实际会发生什么。

？

profit = value if value > profit
end
profit
end

一百万感谢

Answer 1

数组的#max方法返回数组中的最大值，因此...[3, 7, 4].max将返回7(最大值)

value = [0, value].max 

这基本上是返回较大的(零或value)并将其分配给value。 因此，它将value中的任何负量替换为零，但如果它是正值，则保留它。

做同样事情的另一种方法...

value = 0 if value < 0

Answer 2

注意条件you must buy before you sell，所以基本上我们在最大利润中找到最大值(每个利润i是每个价格[i]和i之后的价格之间的差异之间的最大值)

所以一个朴素的解决方案是 2 个循环

max of [
max-profit-0: max of p[1] - p[0], p[2] - p[0], ...
max-profit-1: max of p[2] - p[1], p[3] - p[2], ...
....
]

但是您提供的解决方案非常出色，它只需要利用以下优点进行一个循环：

价格

• 0 和价格 2 之间的利润 =

  = p[2] - p[0] == (p[1] - p[0]) + (p[2] - p[1])=>这是value += (prices[i] - prices[i-1])做的代码，它将计算当前日期 j(当前步骤)和开始日期 i 之间的利润 只要不同还是积极的。

• 如果上面的总和在步骤 1 和 2 为正：p[1] - p[0] > 0和p[1] - p[0] + p[2] - p[1] > 0，这意味着p[0] < p[1]和p[0] < p[2]，我们可以得出结论，对于日期 2 (j>2) 之后的每个p[j]，p[j] - p[0]总是大于p[j] - p[1]和p[j] - p[2]，因此我们可以继续计算起始指数为 0 的总和(利润)并忽略 1 和 2， 因为这个问题的目标是找到 MAX，对吧？

只要值为正，代码value = [0, value].max就会返回值，然后值继续前进。

• 如果上面的总和(或利润)在步骤 1 为正，在步骤 2 为负：(p[1] - p[0]) + (p[2] - p[1]) < 0如此p[2] - p[0] < 0和p[1] - p[0] > 0，这意味着p[2] < p[0]和p[0] < p[1]。

• 所以我们有p[2] < p[0] < p[1]，显然对于日期 2 (j>2) 之后p[j]的每个价格，p[j] - p[2]总是大于p[j] - p[0]和p[j] - p[1]，因此我们可以忽略 p[0] 和 p[1]，因为这个问题的目标是找到 MAX，对吧？

  这就是为什么我们可以将value重置为零以再次开始计算利润 使用起始索引 2，现在来自下一个循环中的代码value += (prices[i] - prices[i-1])的值实际上是p[3] - p[2]，而不是p[3] - p[2] + p[2] - p[1]...，请记住我们已经缓存了范围 [0..2] 的最大利润。

  这就是value = [0, value].max要做的代码，如果值为<= 0，它将返回 0。

[7, 1, 5, 3, 6, 4]
+  - # that mean you sure that profits 
# between each [5, 3, 6, 4] and [7] always < with [1]
# so reset with date 1

很好的解决方案！

Answer 3

理解程序的一个好方法是简单地用笔和纸逐步浏览它，同时跟踪所有(相关)状态。所以，让我们这样做。

在我们的例子中，相关状态是两个局部变量的值profit和value以及迭代变量i和扩展prices[i]和prices[i-1]。我们首先将它们初始化为方法第 1 行和第 2 行中0的值。然后，第 4-8 行是完成所有实际工作的循环;第 10 行只是返回结果。很容易看出，第 5-7 行是完成所有工作的行，因此让我们关注这些：

它有什么作用？<th style="text-align： center;">profitstyle="文本对齐：右;">1style="文本对齐：右;">1style="文本对齐：右;">1style="文本对齐：右;">2style="文本对齐：右;">2style="文本对齐：右;">2style="文本对齐：右;">3style="文本对齐：右;">3style="文本对齐：右;">3style="文本对齐：右;">4style="文本对齐：右;">4style="文本对齐：右;">4style="文本对齐：右;">5style="文本对齐：右;">5style="文本对齐：右;">5

i	line	code
value	prices[i]	prices[i-1]
5	value += (prices[i] - prices[i-1])	将价格差异添加到当前值	0	0 -6 = -6	7	1
6	value = [0, value].max	将value设置为0及其当前值的最大值，IOW 设置为0value如果为负数	0	0	7	1
7	profit = value if value > profit	profit设置为其当前值的最大值并value	0	0	7	1
5	value += (prices[i] - prices[i-1])	将价格差异添加到当前值	0	0 + 4 = 4	1	5
6	value = [0, value].max	<value设置为0及其当前值的最大值，IOW 将value设置为0如果它是负数	0	4	1td style="文本对齐：居中;">5
7	profit = value if value > profit	profit设置为其当前值的最大值，value	4	4	1	5
5	value += (prices[i] - prices[i-1])	将价格差异添加到当前值	4	4 - 2 = 2	5	3
6	value = [0, value].max	value设置为最大值0及其当前值，IOWvalue设置为0，如果它是负数	4	2	5	3
7	profit = value if value > profit	profit设置为其当前值的最大值，value	4	4	5	3
5	value += (prices[i] - prices[i-1])	将价格差异添加到当前值	4	2 + 3 = 5	3	6
6	value = [0, value].max	将value设置为0及其当前值的最大值，IOW 设置为value如果为负数<则设置为0td style="文本对齐：居中;">4	5	3	6
7	profit = value if value > profit	profit设置为其当前值的最大值，value	5	5	3	6
5	value += (prices[i] - prices[i-1])	将价格差异添加到当前值	5	5 - 2 = 3	6	4
6	value = [0, value].max	value设置为最大值0及其当前值，IOW 如果为负数，则 IOWvalue设置为0	5	3	6	4
7	profit = value if value > profit	profit设置为其当前值的最大值，value	5	3	6	4