允许连续买入或卖出时买入和卖出股票的最佳时间

Question

给你n天的股票价格。通过股票交易获得最大利润。你每天最多只能交易一次：每天你可以选择购买一只股票，或者卖出一只股票（如果你有），或者放弃当天的交易，什么都不做。

给定a=[1,2,10,9]，返回16

解释：

你可以在第一天和第二天购买，在第三天和第四天出售。

利润：-1-2109=16

给定a=[9,5,9,10,5]，返回5

解释：

你可以在第二天买入，第四天卖出。

利润：-5 10=5

困难的部分是，你可以进行连续的买入和/或卖出，这意味着一旦你持有一只股票，你不一定要在买入另一只之前卖出它。

我的想法是以下算法：

从最大价格开始，然后匹配输入数组中最大价格之前出现的最小价格。匹配后，从数组中删除这两个价格，并继续重复此过程，直到找不到匹配的价格。这个算法似乎是可行的，但它需要O（n²）时间，这还不够快。

如何用更好的时间复杂度来解决这个问题，例如O（nlogn）？

Answer 1

更正：我的逻辑失败了（因为[9, 12, 1, 18, 17, 13, 1, 2, 10]给了29而不是35）...

这是我想出的逻辑：

1. 将arr a映射为{值、日期和关系}的arr。
2. 将第一个关系设置为“更小”，与上一个相比，以下关系设置为“更小”|“相等”|“更大”。
3. 从开始，找到最后一个连续的“更小”（然后“更小”|“相等”），从那里，找到最后一个连续的“更大”，匹配（推动买卖数组）并删除。
4. 从2开始重复，直到所有都没有“变大”或长度

Answer 2

这是一个O（n²）算法。因此，从这个意义上说，它并不能以渐进更快的速度回答你的问题，但正如你在一篇评论中了解到的，你的算法将不起作用，我相信它可能还是有用的。

我会选择动态规划。迭代几天，并维护一个列表，其中指数描述了你拥有的股票数量，其价值是在这种情况下达到的最佳现金余额。因此，从列表开始，它是[0]，也就是说，一个条目表明你可以在余额为零的情况下拥有零库存。

每一天，你都可以购买、出售或跳过。你可以用这样的方式表达所有这些：

balance_new[i] = max(balance[i], balance[i-1] - quote, balance[i+1] + quote)

第一项代表跳过：保持当前库存和余额。第二项代表买入：你获得一只股票（从i-1到i），但按当日价格减少余额。第三个条目是卖出：你减少一只股票，但将当前价格增加到你的余额。

您从中获得的balance_new将成为第二天的余额。您需要注意列表的边界，其中一个表达式将无效，因为它会索引出界。您无法通过买入操作获得零库存。请求的最大利润是处理完所有天数后的余额[0]。它代表让您没有库存的最大余额。

你有一个外环在n天内迭代。一个内环迭代你可能拥有的股票数量。这个数字在每次迭代中都是线性增长的。如果你愿意，你可以试着聪明一点，在你达到外环步骤的一半后，将内环的步骤减少一个。这是因为在最后获得比你能卖的更多的股票永远不会有回报。所以内环中的步骤数量会从1到n/2，然后再次下降，总共是n²/4 O（n），但总的来说仍然是O（n²）。

Answer 3

我们可以将其建模为最小成本循环问题，并使用类似于您的想法的专用O（n log n）时间算法优化解决它。

在流量网络中，每天有一个节点，一个节点代表市场。每天有两个单位容量弧，一个来自市场，成本等于当天的价格，一个来自市场，成本等于减去价格。有零成本和无限容量的弧可以将流量从每天（最后一天除外）转移到之后的一天。这些代表持有股份。

使用（）表示节点，==

      0        0        0
 ()======>()======>()======>()
 ^\       ^\       ^\       ^\
1| |-1   2| |-2  10| |-10  9| |-9
  \v       \v       \v       \v
  (                            )

从技术上讲，在这种重新制定的方案中，在同一天进行买卖是可能的，但这不是一个有利可图的举动，所以这无关紧要。

给定一个残差网络，该理论（线性规划对偶）说，当且仅当没有负成本简单循环时，我们就完成了。这种循环的直观含义正是你所期望的：购买股票并在以后盈利出售。

该算法通过在k的第一个k天从1到n连续消除所有负成本简单循环（从现在开始的盈利循环）来工作。在基本情况下，仅第一天是永远不会盈利的，因此我们可以继续进行归纳步骤。

对于归纳步骤，我们知道在第一个k-1天没有盈利周期，并希望将其扩展到k。如果在第一个k天有一个盈利周期，它涉及在第k天销售。但是买什么？我们可以通过保持剩余购买机会的最小优先级队列来有效地回答这个问题。我们将日k价格与队列min进行比较，如果它更高，我们就进行交易，这涉及弹出min并推动日k价格，因为从剩余网络的角度来看，取消我们的销售看起来与购买股票相同。然后我们推动日k价格，而不管它是否代表在日k实际购买的可能性。

我们必须谨慎行事，证明我们不仅仅是引入了另一个盈利周期。这就是选择min的原因：我们不能将新的“销售”（实际上取消了购买）机会与任何剩余的购买机会结合起来，因为新的销售价格不高于任何这些机会。

完成的算法非常简单。在Python中：

import heapq


def trading_profit(prices):
    profit = 0
    queue = []
    for price in prices:
        if queue and queue[0] < price:
            profit += price - queue[0]
            heapq.heapreplace(queue, price)
        heapq.heappush(queue, price)
    return profit