在采访一家初创公司时，有人问我这个问题，最近在
Code Sprint:systems
**问题:
为您提供了几天的股票价格。每天，您可以购买一个单位的股票，出售已经购买的任何数量的股票单位，或者什么都不做。通过最佳规划交易策略可获得的最大利润是多少？**
示例(输入内容，即天数可以变化)
5 3 2 =>利润= 0 //由于价格每天都在下降，因此我们可以赚取的最大利润= 0
1 2 100 =>利润= 197
1 3 1 2 =>利润= 3 //我们以1的价格在3卖出，然后我们以1的价格买入，然后以2卖出..总利润= 3
我的解决方案:
a)查找股票价格最高的日子。直到当天继续购买1个单位的库存。
b)如果该天是最后一天，则退出:
其他:
卖出当天的所有股票，然后在当天之后拆分数组，然后递归其余元素
c)合并利润
例如1 4 1 2 3
a)第2天的最高股价..因此，我们在第1天买入股票，并在第2天卖出股票(利润= 3)，然后在剩余的天数递归:1 2 3
b)最大价格为3(第5天)，因此我们在第3天和第4天继续购买股票，并在第5天卖出(利润=(3 * 2-3-= 3)
c)总利润= 3 + 3 = 6
结果复杂度为O(n ^ 2)。此解决方案通过了11个案例中的10个，但超过了最后一个测试案例的时间限制(即最大的输入)
所以我的问题是，有人能想到一个更有效的解决方案吗？有没有动态编程解决方案？
附注:这是我第一次在这里提问。所以请让我知道我是否需要改进/添加此问题
最佳答案
我同意您方法的逻辑，但无需进行递归处理或全局最大值搜索。要查找卖/买日，您只需每天查看一次:
诀窍是从头开始。 如果您的旅行时间倒退，股票交易将很容易!
如果您认为代码比单词更容易阅读，请跳过我的解释，但是这里有:
从末尾看，看当天的价格。这是到目前为止(从头到尾)的最高价格，然后出售!最后一天(我们开始阅读的地方)将始终出售。
然后转到第二天(记住，时间倒退)。这是目前为止最高的价格吗？ -然后全部出售，您将找不到更好的一天。其他价格上涨，因此购买。继续以同样的方式直到开始。
整个问题可以通过一个反向循环来解决:计算决策和交易利润。
这是类似C的python中的代码:(我避免了大多数pythonic的东西。对于C人来说应该可读)
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:在那一点之后，我们的价格下降或稳定，因此没有购买。您可以通过一个简单的循环来验证利润计算是否正确(为简单起见，假设它在上述函数中)
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)
关于algorithm - 给定股票报价的利润最大化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9514191/