递归计算股票最大收益:递归调用及i-1、j+1边界参数疑问
两个递归调用的组合作用
这段代码的逻辑支持多次不重叠交易(即必须卖出已有持仓后才能再次买入,不能同时持有多支股票),计算全时间段内所有合法交易的最大总利润。
当程序遍历到假设的交易组合「第i天买入、第j天卖出」时:
price[j] - price[i]是这笔固定交易本身的利润- 两个递归调用的作用,是分别计算这笔交易完成前后两个独立时间段的最大可获利润:
- 左侧递归
max_profit(price, start, i - 1):计算从起始位置到本次买入日之前的时间段,所有合法交易能拿到的最大利润 - 右侧递归
max_profit(price, j + 1, end):计算从本次卖出日之后到终止位置的时间段,所有合法交易能拿到的最大利润
三者相加,就是当前这笔i买j卖的交易,搭配前后所有能做的其他交易的总收益。程序会遍历所有可能的i、j组合,最终取所有组合里的最大收益值。
- 左侧递归
为什么用i-1和j+1作为递归边界
核心原因是保证交易时间区间的互斥性,避免交易日被重复占用:
- 对于左侧递归的边界
i-1:
本次交易已经把i天作为买入操作日,i天不能再被划入前半段的可交易区间。如果直接用i作为右边界,i天会被同时算入前半段递归的交易范围和当前交易的买入日,既会造成冗余的重复计算,也违背了交易日操作唯一归属的设计逻辑——前半段的所有交易必须在本次买入前完全结束,最晚只能到i-1天。 - 对于右侧递归的边界
j+1:
本次交易已经把j天作为卖出操作日,j天不能再被划入后半段的可交易区间。如果直接用j作为左边界,j天会被同时算入后半段递归的交易范围和当前交易的卖出日,同样会出现重复计算、操作重叠的问题——后半段的所有交易必须在本次卖出后才开始,最早只能从j+1天启动。
补充说明:这种边界设计不会漏掉合法的交易场景。因为“当天卖出后立刻买入”的操作,本质上的收益和“前一天卖出、当天买入”是等价的,不会因为排除了i、j两个点就损失最优解,反而能大幅减少递归的重复计算量。
内容的提问来源于stack exchange,提问作者baki hussain
相关产品推荐
相关产品推荐

