给定股票报价最大化利润

Question

我在面试创业公司时被问到这个问题,并在最近的比赛中再次看到了这个问题

Code Sprint:系统

**问题:

您将获得一组天的股票价格.每天,您可以购买一个单位的股票,出售已经购买的任何数量的股票单位,或者什么也不做.通过最佳规划您的交易策略可以获得的最大利润是多少？**

示例(输入即天数可以变化)

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个但超过了最后一个测试案例的时间限制(即最大的输入)

所以我的问题是,任何人都可以想到一个更有效的解决方案吗？有动态编程解决方案吗？

PS:这是我第一次在这里提问.所以如果我需要改进/添加这个问题,请告诉我

Answer 1

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

诀窍是从头开始.如果您的旅行倒退,股票交易很容易!

如果您认为代码比单词更容易阅读,请跳过我的解释,但是这里有:

从最后阅读,看看那天的价格.这是迄今为止的最高价格(从结束),然后卖!最后一天(我们开始阅读)你将永远卖出.

然后去第二天(记住,及时倒退).它是迄今为止的最高价格(从我们所看到的所有)？ - 然后卖掉所有,你将找不到更美好的一天.否则价格上涨,所以买.继续以同样的方式直到开始.

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

这是C-like 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)

Answer 2

另一种看待它的方法:
在预处理中,对于每个元素a[i]找到a[j]st j > i 并且它最大化,(a[j] - a[i])
所以,你可以做的最好的价格a[i]是买入a[i]和卖出a[j].如果没有a[j]st a[j] > a[i]则a[i]根本不是买点.

预处理时间: O(N)

S[N-1] = A[N-1];
for(int i=N-2; i>=0; --i)
       S[i] = max(A[i], S[i+1]);

在这里,S [i]是您应该卖出[i]的价格.

总结利润总额: O(N)

long long int Profit = 0;
    for(int i=0;i<N;++i)
          Profit += max(0,  (S[i]-A[i]) );