algorithm - 最大化给定股票报价的利润

Question

<分区>

Answer 1

我同意你方法的逻辑，但不需要进行递归处理或全局最大值搜索。要查找卖出/买入日，您只需每天查看一次:

诀窍是从头开始。 如果您时光倒流，股票交易会很容易!

如果你认为代码比文字更容易阅读，请跳过我的解释，但这里是:

读到最后，看当天的价格。这是目前为止(从末尾算起)的最高价吗，那就卖吧!最后一天(我们开始阅读的地方)你总是会卖出。

然后转到第二天(记住，时间向后)。这是迄今为止的最高价格吗(从我们看过的所有价格来看)？ - 然后全部卖掉，你不会找到更好的日子。否则价格上涨，所以买。以同样的方式继续，直到开始。

整个问题通过一个反向循环解决:计算决策和交易利润。

这是类 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)