纵有疾风起
人生不言弃

详解股票买卖算法的最优解(二)


前言

今天王子与大家继续分享LeeCode上有关如何买卖股票获取最高利润的题目。

本文作为补充文章,对更复杂的题目进行解答,如果还没有阅读上篇文章,希望小伙伴们先去看一下上篇文章:详解股票买卖算法的最优解(一),有助于理解。

上篇文章我们讲解了根据状态机、状态转移方程思考问题,解决了4道有关股票买卖的题目,今天我们再来看两道复杂的题目。

请看下面的题目:

详解股票买卖算法的最优解(二)插图

 

 

 这道题目包含了几乎所有的情况,下面我们来进行分析。

 

第一题,k=2,即最多交易两次

k=2和之前题目就不一样了,之前是不需要考虑k的情况的,但是这道题是要把k放到考虑范围内的,状态转移方程不能化简,就是最开始分析的样子,但稍微有些不同的是k值什么时候加一,之前的文章我们说当每次buy的时候k加一,为了后文更好理解我们现在把k加一这一操作放到sell操作后,也就是说卖出后才算一次完整的交易,k才会加一,所以转移方程如下:

dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);

如果按照之前的解题方法,很容易会写成下边这种代码:

int k=2;int[][][] dp=new int[n][k+1][2];for(int i=0;i<n;i++){  if(i=0){处理特殊值};  dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);  dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);  }return dp[n-1][2][0];

但这样是错误的,还记得我们前文提到的穷举框架吗,穷举的是所有的状态,之前我们不用考虑k,但是这道题目考虑了k就要对k再进行穷举。

我们先逐一分析特殊情况,有助于理解:

dp[i][0][0]:表示第i天交易了0次时的空仓状态
dp[i][0][1]:表示第i天交易了0次时的持有状态
dp[i][1][0]:表示第i天交易了1次时的空仓状态
dp[i][1][1]:表示第i天交易了1次时的持有状态
dp[i][2][0]:表示第i天交易了2次时的空仓状态
dp[i][2][1]:表示第i天交易了2次时的持仓状态(也就是第三次交易已经买入了,实际不存在这种情况,交易了两次后不能再交易,所以一定是空仓状态)

对于上边的情况我们再做一个分析:

dp[i][0][0]:对应于初始状态,第i天0次交易,空仓状态,利润一定是0
dp[i][0][1]和dp[i][1][0] 这两个是一对,对应的就是第一次买入、第一次卖出(卖出的时候才会增加交易次数)。
dp[i][1][1]和dp[i][2][0] 这两个也是一对,对应的就是第二次买入、第二次卖出。
dp[i][2][1]对应的是第三次的买入,因为我们限定了买入次数最多为两次,所以这种情况不存在。

接下来我们再详细分析一下第一次买卖的状态转移方程

第一次买入:从初始状态转换而来,或者第一次买入后保持不动dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i])第一次卖出:从第一次买入转换而来,或者第一次卖出后保持不动dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1]+prices[i])

第二次买卖的状态转移方程:

第二次买入:从第一次卖出转换而来,或者第二次买入后保持不动dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0]-prices[i])第二次卖出:从第二次买入转换而来,或者第二次卖出后保持不动dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1]+prices[i])

我们把第一次买卖、第二次买卖的转移方程合到一起,就得到了最后的结果。
同时还要处理特殊情况的特殊值。
最后求的利润最大值就保存在 dp[n-1][0][0]、dp[n-1][1][0]、dp[n-1][2][0]中,我们求出这几个值的max再返回就可以了。

为什么我们考虑最大利润要把dp[n-1][0][0]这种情况算上呢,因为如果股市价格类似[5,4,3,2,1],这种一直下跌的情况,不交易的利润是0,而交易了一定是亏损的。

直接看代码

    public int maxProfit(int[] prices) {        int n = prices.length;        int max=0;        //定义三维数组,第i天、交易了多少次、当前的买卖状态        int[][][] dp = new int[n][3][2];        for(int i=0;i<n;i++) {          for(int k=0;k<=2;k++){            if(i==0){                dp[i][k][0]=0;                dp[i][k][1]=-prices[i];                continue;            };            dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);            if(k==0){                dp[i][k][0] = dp[i-1][k][0];            }else{                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);            }          }         }        for(int k=0;k<=2;k++){            if(max<dp[n-1][k][0]){                max=dp[n-1][k][0];            }        }        //返回最大值        return max;    }

 

有了状态转移方程的概念,想看懂上边的代码其实不难,但是如果把变量名全都改成a,b,c,d,我估计大多数人都会看着你的代码脑壳生疼。

好了,我们再来看下一题。

第二题,k=任何值,即交易次数限制是动态获取的

这题和 k = 2 没啥区别,解法基本相同。但是需要考虑k值的取值范围,k值不能无限大。想一想,k值也就是交易次数有什么限制呢?

一次交易由买入和卖出构成,至少需要两天。所以说有效的限制次数 k 应该不超过 n/2,如果超过,就没有约束作用了,相当于 k = +infinity。这种情况是之前解决过的。

所以可以套用之前的k=+infinity的算法

最终结果如下:

public int maxProfit(int max_k, int[] prices) {        if(prices.length==0){            return 0;        }        int n = prices.length;        if(max_k>n/2){            return maxProfit(prices);        }        int max=0;        //定义三维数组,第i天、交易了多少次、当前的买卖状态        int[][][] dp = new int[n][max_k+1][2];        for(int i=0;i<n;i++) {          for(int k=0;k<=max_k;k++){            if(i==0){                dp[i][k][0]=0;                dp[i][k][1]=-prices[i];                continue;            };            dp[i][k][1] = Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i]);            if(k==0){                dp[i][k][0] = dp[i-1][k][0];            }else{                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k-1][1]+prices[i]);            }          }         }        for(int k=0;k<=max_k;k++){            if(max<dp[n-1][k][0]){                max=dp[n-1][k][0];            }        }        //返回最大值        return max;    }    public int maxProfit(int[] prices) {        int n=prices.length;        int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;        for(int i=0;i<n;i++){            int temp=dp_i_0;            dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);            dp_i_1=Math.max(dp_i_1,temp-prices[i]);        }        return dp_i_0;    } 

至此,算上上篇文章的4道题目,一共6到关于股票买卖的问题已经全部解决。

 

总结

好了,关于股票买卖算法的最优解系列就告一段落。

这类题型的解题思路就是引入了状态转移方程的概念,现在我们一起弄懂了这种解题思路,是不是还有一点小成就感呢。

解决这类问题的关键就是确认有几种选择,确定有几种状态,设定状态转移方程,处理特殊情况的值。之后就是套用进代码,解决问题。

希望大家再做算法题的时候脑子里能回忆起这种框架的解题思路。

如果觉得文章内容对你有所启发,希望点个赞,我们后续还会有很多内容与大家分享,不见不散。

 

往期文章推荐:

中间件专辑:

什么是消息中间件?主要作用是什么?

常见的消息中间件有哪些?你们是怎么进行技术选型的?

你懂RocketMQ 的架构原理吗?

聊一聊RocketMQ的注册中心NameServer

Broker的主从架构是怎么实现的?

算法专辑:

和同事谈谈Flood Fill 算法

详解股票买卖算法的最优解(一)

详解股票买卖算法的最优解(二)插图(1)

 

文章转载于:https://www.cnblogs.com/lm970585581/p/13633254.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 详解股票买卖算法的最优解(二)

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活