允许连续买卖时买卖股票的最佳时机

Question

问题

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

示例 1：

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

解释：

您可以在第 1 天和第 2 天买入，并在第 3 天和第 4 天卖出。

利润：-1-2+10+9 = 16

示例 2：

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

解释：

您可以在第 2 天买入并在第 4 天卖出。

利润：-5 + 10 = 5

我的分析

困难的部分是您可以连续买入和/或卖出，这意味着一旦您拥有一只股票，您不必在购买另一只股票之前将其卖出。

我的想法是以下算法：

从最大价格开始，然后匹配输入数组中出现在该最大价格之前的最小价格。匹配后，从数组中删除这两个价格并不断重复此过程，直到找不到更多匹配为止。看起来这个算法是有效的，但它花费了O(n ² )时间，这还不够快。

题

如何用更好的时间复杂度来解决这个问题，比如O(nlogn)？

Answer 1

我们可以将其建模为最小成本流通问题，并使用与您的想法类似的专门的 O(n log n) 时间算法以最佳方式解决它。

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

使用()代表节点，==>代表无限容量弧和-->代表单位容量弧和标注的费用，您的样品实例

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

从技术上讲，在此重新制定中，可以在同一天买卖，但这不是有利可图的举动，因此无关紧要。

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

该算法的工作原理是在从到的第一k天连续消除所有负成本的简单周期（从现在开始的盈利周期）。在基本情况下，单独的第一天永远不会盈利，因此我们可以进入归纳步骤。k1nk = 1

对于归纳步​​骤，我们知道在最初k-1几天没有盈利周期，并希望将其扩展到k。如果在第一k天有盈利周期，则涉及第天卖出k。但是买什么？我们可以通过维护剩余购买机会的最低优先级队列来有效地回答这个问题。我们将当天k价格与排队分钟进行比较，如果它更高，我们就进行交易，这涉及弹出分钟并推动当天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

Answer 2

这是一个 O(n\xc2\xb2) 算法。因此，从这个意义上说，它并不能以渐进更快的方式回答您的问题，但正如在评论中您了解到您的算法不起作用一样，我相信它仍然可能有用。

\n

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

\n

对于每一天，您都可以购买、出售或跳过。您可以使用如下方式将所有内容一起表达：

\n

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

\n

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

\n

balance_new你从中得到的结果将成为balance第二天的结果。并且您需要注意列表的边界，其中一个表达式会变得无效，因为它会索引越界。您无法通过购买操作使库存为零。所要求的最大利润是balance[0]在您处理完所有天之后。它代表您没有库存的最大余额。

\n

您有一个迭代 n 天的外循环。还有一个内循环迭代您当时可能拥有的潜在库存数量。该数字在每次迭代中线性增长。如果您愿意，可以尝试聪明一点，在达到外循环步数的一半后，将内循环步数减少 1。这是因为购买的股票永远不会超过你最终可以出售的股票。因此，内部循环中的步数将从 1 变为 n/2，然后再次下降，总共为 n\xc2\xb2/4 + O(n)，但仍然是 O(n\ xc2\xb2) 总而言之。

\n