• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

123. 最佳时间买卖股票(仅限N次)

leetcode admin 6个月前 (04-07) 528次浏览 0个评论 扫描二维码

假设您有一个数组,其中第 i 个元素是第 i 天给定股票的价格。

设计算法以找到最大利润。 您最多可以完成两笔交易。

注意:您不得同时进行多笔交易(即,您必须在再次购买之前卖出股票)。

例 1:

输入:[3,3,5,0,0,3,1,4]
产量:6
说明:在第 4 天买入(价格= 0)并在第 6 天卖出(价格= 3),利润= 3-0 = 3。
然后在第 7 天买入(价格= 1)并在第 8 天卖出(价格= 4),利润= 4-1 = 3。
例 2:

输入:[1,2,3,4,5]
产量:4
说明:在第 1 天买入(价格= 1)并在第 5 天卖出(价格= 5),利润= 5-1 = 4。
请注意,您不能在第 1 天购买,在第 2 天购买并在以后出售,就像您一样
同时参与多个交易。 您必须在再次购买之前出售。
例 3:

输入:[7,6,4,3,1]
输出:0
说明:在这种情况下,没有进行任何交易,即最大利润= 0。

 

解法

因为之前做过一导 easy 的题,它是只允许你成交一次,然后获取最大的利润,这道题最大交易次数只允许交易两次,那么我一开始的想法是这个样子:

  • 先算出只交易一次的最大利润 max_profit_once
  • 遍历每一天,计算当前第 i 天之前与第 i+1 天以后两者最大利润之和即 left_profit+right_profit
  • 然后比较第二步与第三步利润大小,返回最大值即可

这个测试的代码提交以后在 200 个 case 中第 199 个 case 失败了,原因在于超时了

第 199 个 case 是一个很长的测试样例,因此使用之前的方法穷举获取很耗时。

dp 动态规划

这道题是一个动态规划题,既然涉及到动态规则规划那就要知道我们现在求解的大问题是啥,如何拆分成小问题?

  • 大问题就是 N 天内限定最大两次交易的情况下我们能够获取的最大利润
  • 小问题:

从上面图可以看出当我们在 Day5 发生交易的时候,此时是处于第 M 次卖出交易,那么之前肯定在某一天发生买入交易,图中给出了 Day3 发生买入交易,那么第 M 次交易产生的最大收益可以获知。那么剩下的就是要去求解第 M-1 次交易获取的最大收益,按照图示的例子就是要去计算 Day1 和 Day2 产生的收益,如果时间的跨度更长,那么我们会一直计算到第一次交易获取的利润

累加 M 次交易获取的利润之和(存在多种情况下 M 次交易之和),取出最大值就得到我们想要的答案了

所以我们可以得到下面的公式:

Profit(T,M)=Profit(T-n,M-1)+Profit(T-n-m,M-2)+…..

解法

代码说明

第一个 if  判断就是当 prices 列表长度小于 2 的时候直接返回 0,因为你们有任何机会去出手交易。

m 就是我们定义的交易最大次数,该题是 2 次

DP 是我们定义的保存第 m 次以及第 N 天交易获取的最大利润矩阵,为什么会定义[m+1,N]维,这在后面迭代计算的时候

会用到,初始化就是矩阵里面所有的元素都为 0

第一个 for 循环是循环迭代交易次数,即仅在 i 次交易内得到的最大利润

第二个 for 循环是迭代所有的天数,因为可以在任意一天发生交易

if i == 0 or j == 0

该子嵌套条件说明,当交易次数为 0 的时候或者第一天开盘,你只能买入没法卖出,所以满足此条件下的利润值都是为 0

的,因为你都不满足交易的条件

所以只有在当交易次数 i 为 1 且 j>0 的时候开始才开始有机会交易,那么就到了嵌套 else 处理部分了

DP[i][j] = DP[i][j - 1]

DP[i][j] 直接使用 DP[i][j – 1] 赋值,只是相当于初始化,当前第 j 天你不卖出交易,那么你的利润就是昨天的利润。

接下来循环遍历 k , k 的取值返回是  0 到 j-1

意思就是在 0 到 j-1 天内,用户必须在这其中一个买入,然后在第 j 天卖出

prev 变量是获取第 i-1 次第 k-1 天 获取的最大利润,因为当前是第 i 次交易,我们要的是总的最大利润,所以我们要把之前的利润都要加起来。

DP[i][j] = max(DP[i][j], prev + prices[j] - prices[k])

这一步:还记得在算 DP[i][j] 之前我们使用 j-1 天的数据初始化了一下

prev + prices[j] – prices[k]  就是第 j 天获取的最大利润了,但是我们也要跟前一天的数据比较,因为这天交易可能是亏的,如果亏损了,那么证明今天不适合交易,那么还是保留之前的交易记录,当然 j 天的利润还是沿用之前的利润数据,同时第 j 天就不应该发生卖出交易。

k 值循环就是在寻找局部最优解,就相当于 DP 问题小问题求解优化。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)<2:
            return 0
        
        m = 2
        n = len(prices) 
        DP = [ [0]*n for x in range(m+1)]
        for i in range(m+1):
            for j in range(n):
                if i == 0 or  j == 0:
                    DP[i][j] = 0
                else:
                    DP[i][j] = DP[i][j - 1]
                    for k in range(j):
                        
                        prev =  0 if  k == 0  else DP[i - 1][k - 1]
                        DP[i][j] = max(DP[i][j], prev + prices[j] - prices[k])
           
        return DP[m][n - 1]

 

优化

看完上面是不是觉得这个问题已经可以解决了,此时如果你提交上面的代码仍然是 Fail,依然会提示你超时,也是发生在第 199 个 case,因为你在时间复杂度是 O(kn^2)

下面代码与之前的不同点就是在于 k 循环的优化

其实按照现在的代码逻辑我们每一步都是局部最优,那么我们在计算 DP[i][j] 就只使用

DP[i][j-2]-prices[j-1]+prices[j]与 DP[i][j-1]即可,至此完成了这道题的求解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)<2:
            return 0
        
        m = 2
        n = len(prices) 
        DP = [ [0]*n for x in range(m+1)]
        for i in range(m+1):
            tempMax=-sys.maxsize-1
            for j in range(n):
                if i == 0 or  j == 0:
                    DP[i][j] = 0
                else:
                    prev = 0
                    if j >= 2:
                        prev = DP[i - 1][j - 2]
                    tempMax =max(tempMax, prev - prices[j - 1])
                    DP[i][j] = max(DP[i][j - 1], tempMax + prices[j])
           
        return DP[m][n - 1]
  

 

 

 


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明123. 最佳时间买卖股票(仅限 N 次)
喜欢 (1)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!