最大化给定股票报价的利润 [英] Maximizing profit for given stock quotes
问题描述
我在面试一家初创公司时被问到这个问题，并在最近的比赛中再次看到了这个问题
I was asked this question while interviewing for a startup and saw this again in the recent contest at
**问题:
您将获得一组天数的股票价格.每天，您可以购买一个单位的股票，也可以卖出您已经购买的任意数量的股票单位，或者什么也不做.通过最佳地规划您的交易策略，您可以获得的最大利润是多少?**
You are given the stock prices for a set of days . Each day, you can either buy one unit of stock, sell any number of stock units you have already bought, or do nothing. What is the maximum profit you can obtain by planning your trading strategy optimally?**
示例(输入即天数可能会有所不同)
Examples ( The input i.e the no of days can vary )
5 3 2 =>利润 = 0//由于价格每天都在下降，我们可以赚取的最大利润 = 0
5 3 2 => profit = 0 // since the price decreases each day ,the max profit we can make = 0
1 2 100 =>利润 = 197
1 2 100 => profit = 197
1 3 1 2 =>利润 = 3//我们以 1 买入 以 3 卖出，然后以 1 买入并以 2 卖出 ..总利润 = 3
1 3 1 2 =>profit = 3 // we buy at 1 sell at 3 , then we buy at 1 and sell at 2 ..total profit = 3
我的解决方案:
a) 找出股价最大的那一天.继续购买 1 单位的股票直到那天.
a) Find the day when the stock price was largest . Keep buying 1 unit of stock till that day.
b) 如果那天是最后一天，那么退出:
b) If that day is the last day then quit:
其他:当天卖出所有股票并在当天之后拆分数组并对剩余元素进行递归
c) 合并利润
else:
Sell all the stocks on that day and split the array after that day and recurse on the remaining elements
c) merge the profits
例如 1 4 1 2 3
a) 第 2 天的最高股票价格 .. 所以我们在第 1 天买入股票并在第 2 天卖出(利润 = 3)然后我们在剩余的日子里递归:1 2 3
e.g 1 4 1 2 3
a) highest stock price on day 2 .. so we buy stock on day 1 and sell it on day 2 ( profit = 3 ) then we recurse on the remaining days : 1 2 3
b) 最高价格是 3(第 5 天)所以我们在第 3 天和第 4 天继续买入股票并在第 5 天卖出(利润 = ( 3*2 - 3 = 3 )
b) Max price is 3 ( on day 5) so we keep buying stock on day 3 and day 4 and sell on day 5 ( profit = ( 3*2 - 3 = 3 )
c) 总利润 = 3 + 3 = 6
c) Total profit = 3 + 3 = 6
结果证明它的复杂性是 O(n^2) .此解决方案通过了 11 个案例中的 10 个，但超过了最后一个测试案例(即最大输入)的时间限制
The complexity for this turns out to be O(n^2) . this solution passed 10 of the 11 cases but exceeded the time limit on a last test case (i.e the largest input)
谁能想出更有效的解决方案来解决这个问题?有没有动态规划解决方案?
Can anyone think of a more efficient solution to this problem? Is there a dynamic programming solution ?
推荐答案
我同意你方法的逻辑，但不需要进行递归处理或全局最大值搜索.要找到卖出/买入天数，您只需每天查看一次:
I agree with the logic of your method but there is no need to do recursive processing or global maxima searches. To find the sell/buy days you just need to look at each day once:
诀窍是从头开始.如果时间倒退，股票交易很容易！
如果您认为代码比文字更容易阅读，请跳过我的解释，但这里是:
If you think code is easier to read than words, just skip my explanation, but here goes:
读到最后，看当天的价格.这是迄今为止(从最后)的最高价格，然后卖掉！最后一天(我们开始阅读的地方)您将永远卖出.
Reading from the end, look at price of that day. Is this the highest price so far (from the end), then sell! The last day (where we start reading) you will always sell.
然后去第二天(记住，时间倒退).它是迄今为止最高的价格吗(从我们看过的所有内容来看)?- 然后卖掉所有，你不会找到更好的一天.否则价格上涨，所以买.以同样的方式继续直到开始.
Then go to the next day (remember, backwards in time). Is it the highest price so far (from all we looked at yet)? - Then sell all, you will not find a better day. Else the prices increase, so buy. continue the same way until the beginning.
整个问题通过一个反向循环解决:计算交易的决策和利润.
The whole problem is solved with one single reverse loop: calculating both the decisions and the profit of the trade.
这是类似 C 的 python 中的代码:(我避免了大多数 pythonic 的东西.对于 C 人来说应该是可读的)
Here's the code in C-like python: (I avoided most pythonic stuff. Should be readable for a C person)
def calcprofit(stockvalues):
dobuy=[1]*len(stockvalues) # 1 for buy, 0 for sell
prof=0
m=0
for i in reversed(range(len(stockvalues))):
ai=stockvalues[i] # shorthand name
if m<=ai:
dobuy[i]=0
m=ai
prof+=m-ai
return (prof,dobuy)
示例:
calcprofit([1,3,1,2]) gives (3, [1, 0, 1, 0])
calcprofit([1,2,100]) gives (197, [1, 1, 0])
calcprofit([5,3,2]) gives (0, [0, 0, 0])
calcprofit([31,312,3,35,33,3,44,123,126,2,4,1]) gives
(798, [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0])
请注意，m 是我们看到的最高股价(从最后开始).如果 ai==m 那么在这一步买入的股票的利润为 0:在那之后我们有下降或稳定的价格并且没有买入.
Note that m is the highest stock price we have seen (from the end). If ai==m then the profit from stocks bought at the the step is 0: we had decreasing or stable price after that point and did not buy.
您可以通过一个简单的循环来验证利润计算是否正确(为简单起见，假设它在上述函数内)
You can verify that the profit calculation is correct with a simple loop (for simplicity imagine it's within the above function)
stock=0
money=0
for i in range(len(stockvalues)):
if dobuy[i]:
stock+=1
money-=stockvalues[i]
else:
money+=stockvalues[i]*stock
stock=0
print("profit was: ",money)
这篇关于最大化给定股票报价的利润的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
