对于给定的股票报价利润最大化 [英] 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 ..total利润= 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 3 1 2 4
一）最高股价第2天..所以大家买的股票在1天，第2天卖了（利润= 2），那么我们递归的剩余天数：1 2 4
e.g 1 3 1 2 4
a) highest stock price on day 2 .. so we buy stock on day 1 and sell it on day 2 ( profit = 2 ) then we recurse on the remaining days : 1 2 4
二）最高价格为4（第5天），所以我们不断地买股票的3天，4天，卖出第5天（利润=（4 * 2 - 3 = 5）
b) Max price is 4 ( on day 5) so we keep buying stock on day 3 and day 4 and sell on day 5 ( profit = ( 4*2 - 3 = 5 )
三）利润总额= 5 + 2 = 7
c) Total profit = 5 + 2 = 7
在这个复杂原来是为O（n ^ 2）。该解决方案通过了10 11例，但超过了一个最后的测试情况下，时间的限制（即最大输入）
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)
所以我的问题是任何人都可以想到的更有效的解决这个问题？的是有一个动态规划的解决方案？
So my question is can anyone think of a more efficient solution to this problem ? Is there a dynamic programming solution ?
PS：这是我第一次问一个问题在这里。所以请让我知道如果我需要改善/添加一些东西到这个问题。
P.S: this is the first time i am asking a question here. so please let me know if i need to improve/add things to this question
推荐答案
我同意你的方法的逻辑，但也没有必要做递归处理或全局最大值搜索。要找到卖/买日子里，你只需要看看在每天一次：
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:
诀窍就是从月底开始。 库存贸易是容易的，如果时间的推移倒退！
The trick is to start from the end. Stock trade is easy if time goes backwards!
如果你觉得code是更容易阅读比的话，只需跳过我的解释，但在这里有云：
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.
这里的code在C-如Python：（我可以避免大部分Python的东西应该是可读的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 range(len(stockvalues)-1,-1,-1): # reverse loop
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 是我们见过的最高股价（从后面）。如果艾==米然后再从个股盈利买的步长为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屋！
