允许连续买卖的最佳买卖股票时间 [英] Best time to buy and sell stocks when allowing consecutive buys or sells

问题描述

问题

您获得了 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

说明:

您可以在第二天买入，在第四天卖出.

利润:-5 + 10 = 5

我的分析

困难之处在于，您可以进行连续的买入和/或卖出，这意味着一旦拥有了股票，就不必在购买另一只股票之前就将其出售.

>

我的想法是以下算法:

从最大价格开始，然后匹配输入数组中最大价格之前出现的最小价格.匹配之后，从数组中删除这两个价格，并继续重复此过程，直到找不到更多匹配为止.该算法似乎可行，但是它花费的时间为 O(n ² )，这不够快.

问题

如何用更好的时间复杂度来解决此问题，例如 O(nlogn)?

解决方案

我们可以将此模型建模为最小成本循环问题，并使用类似于您的想法的专用O(n log n)-时间算法来最佳解决./p>

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

使用()表示节点，使用 ==> 表示无界容量弧，使用-> 表示单位容量弧，并标记成本，您的示例实例为

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

从技术上讲，这种重新制定公式可以在同一天进行买卖，但这并不是有利可图的举动，所以没关系.

给定一个残差网络，该理论(线性规划对偶性)说，当且仅当没有负成本的简单循环时，我们才完成.这种周期的直观含义正是您所期望的:购买股票并在以后出售它获利.

该算法的工作原理是，在头一个 k 天中从 1 依次消除所有负成本的简单周期(从现在开始为盈利周期).code>到 n .在 k = 1 的基本情况下，仅第一天就无法盈利，因此我们可以继续进行归纳.

对于归纳步​​骤，我们知道在前 k-1 天没有获利周期，因此希望将其扩展到 k .如果在前 k 天有一个有利可图的周期，则它涉及在 k 天卖出.但是买什么呢?我们可以通过保留剩余购买机会的最低优先级队列来有效地回答该问题.我们将当天的 k 价格与队列中的分钟价格进行比较，如果价格更高，我们进行交易，这涉及弹出最小值并推动当天的 k 价格，因为从该点开始从剩余网络的角度来看，稍后取消我们的销售看起来就像购买股票一样.然后，无论是否代表实际在天 k 上购买的可能性，我们都会推天 k 的价格.

我们在这里必须小心，并证明我们不仅在引入另一个有利可图的周期.这就是选择最低出价的原因:我们无法将新的销售"出价组合在一起(实际上取消购买)机会与任何剩余的购买机会都是有利可图的，因为新的售价不高于任何这些机会.

完成的算法非常简单.在Python中:

 导入heapqdef trading_profit(价格):利润= 0队列= []价格中的价格:如果queue和queue [0]<价格:利润+ =价格-排队[0]heapq.heapreplace(队列，价格)heapq.heappush(队列，价格)回报利润 

Problem

You're given the n stock prices for n days. Output the maximum profit you can reach by trading stocks. You can only trade at most once a day: on each day you can choose to either buy a single stock, or sell a single stock (if you have one), or give up the trade for that day and do nothing.

Example 1:

Given a = [1,2,10,9], return 16

Explanation:

You can buy on day 1 and 2 and sell on day 3 and 4.

Profit: -1-2+10+9 = 16

Example 2:

Given a = [9,5,9,10,5], return 5

Explanation:

You can buy on day 2 and sell on day 4.

Profit: -5 + 10 = 5

My analysis

The difficult part is that you can engage in consecutive buys and/or sells, meaning that once you posses a stock, you don't necessarily have to sell it before buying another one.

My idea is the following algorithm:

Start from the largest price, and then match the smallest price that occurs before that maximum price in the input array. After matching, remove these two prices from the array and keep repeating this process until you can find no more match. It seems like this algorithm works, but it costs O(n²) time, which is not fast enough.

Question

How could this be solved with a better time complexity, such as O(nlogn)?

解决方案

We can model this as a min-cost circulation problem and solve it optimally with a specialized O(n log n)-time algorithm similar to your idea.

In the flow network, there is a node for each day and a node representing the market. There are two unit-capacity arcs for each day, one from the market with cost equal to the price that day, one to the market with cost equal to minus the price. There are arcs of zero cost and unbounded capacity that can move flow from each day (except the last) to the one after it. These represent holding stock.

Using () to represent nodes, ==> to represent unbounded capacity arcs and --> to represent unit capacity arcs, and labeling the costs, your sample instance is

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

Technically it's possible in this reformulation to both buy and sell on the same day, but that's not a profitable move, so it doesn't matter.

Given a residual network, the theory (linear programming duality) says we're done if and only if there's no negative-cost simple cycle. The intuitive meaning of such cycles is exactly what you would expect: buying a share and selling it profitably later.

The algorithm works by successively eliminating all negative-cost simple cycles (profitable cycles from now on) on the first k days for k from 1 to n. In the base case k = 1, the first day alone is never profitable, so we can move along to the inductive step.

For the inductive step, we know that there are no profitable cycles in the first k-1 days and want to extend that to k. If there is a profitable cycle in the first k days, it involves selling on day k. But what to buy? We can answer that question efficiently by maintaining a min-priority queue of our residual buying opportunities. We compare the day k price to the queue min, and if it's higher we do the deal, which involves popping the min and pushing the day k price, since from the point of view of the residual network, canceling our sale later looks the same as buying a share. Then we push the day k price regardless to represent the possibility of actually buying on day k.

We have to be careful here and prove that we didn't just introduce another profitable cycle. That's the reason to choose the min: we can't combine the new "selling" (actually canceling the buy) opportunity profitably with any of the residual buying opportunities, because the new selling price was not greater than any of those opportunities.

The finished algorithm is pretty simple. In 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

这篇关于允许连续买卖的最佳买卖股票时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！