聊聊买卖股票的最佳时机

前言

大家好，我是大赛哥，好久不见，天天想念！

最近梳理高频动态规划问题，股票问题当然是非常经典的动态规划问题，并且整个系列有好几道题，这里我整理了6道股票系列的经典问题分享给大家，咱们今天聊聊买卖股票的最佳时机。

想当初头一次刷股票问题时候，刷了股票问题一二三，但是完全没用到股票问题的核心思想，当时股票问题一、二不用dp反而也很容易，股票问题三当时自己想到用双向dp过的，完全没get股票问题的核心，这次重新梳理，深入get股票问题的核心思想。

股票问题，一定要理解持有和不持有股票两个相对立状态以及其变化联系。这里持有我用hold表示、不持有用dpSell表示(最后结果基本从不持有中获得)，然后有人将这两个参数整合一个参数数组，[0]表示持有[1]表示不持有，但是个人觉得那样不太直观并且效率没啥区别，所以这里对某些地方不进行优化。

另外dp问题很多时候要设大一位空间、有的从1开始遍历，很多人会混淆0、第0、第1这些东西，这里我为了减少迷糊0号位置(理论是第一个天)我就给它叫第0天统一减少混淆。

虽然说学会了还是不能学会买卖股票，但是学会了能面对面试官，认真看完你一定会有所收获！

买卖股票的最好时机(一)

描述：

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

分析：

股票问题是非常经典的动态规划问题，我们分析题目条件可以找到这些重要信息：

总计只能买一次，也总计只能卖一次
买在卖的前面

根据这个信息其实不用动态规划的思想我们也很容易解决，如果用普通方法也能解决，最笨的方法就是两层循环，第一层枚举每个元素第二层枚举这个元素后面的最大价格的股票，求得最大的股票差即可。

但是那样肯定是会超时的，优化一下一次枚举也可以解决这个问题，就是用一个变量min标记顺序枚举出现过的最小值，用一个变量value记录最大利润，每次枚举的数值和出现过的最小min比较是否更新min，作差比较是否更新最大利润value，最终返回最大利润即可。

实现的代码为：

public int maxProfit (int[] prices) {// write code hereif(prices.length<2)return  0;int value=0;//最大利润int min=prices[0];//记录出现的最小股票for(int i=0;i<prices.length;i++){if(prices[i]<min)//看看是否更新minmin=prices[i];if(prices[i]-min>value)//看看是否更新valuevalue=prices[i]-min;}return  value;
}

时间复杂度：O(n)，空间复杂度：O(1)。

但是这个系列的问题是经典动态规划的问题，我们重点肯定还是要考虑动态规划的方法解决，这里有个持有股票和不持有股票的概念，我们用hold[]表示持有股票，dpSell[]表示不持有股票。hold[i]表示到第i天时持有股票时候的最高利润(这里暂时为负数，因为只能买一次，遇到低的股票值就更新)，dpSell[i]表示第i天不持有股票时候的最大利润（这个利润要么是继承前一天的最大利润，要么是在当天卖了股票获取的利润）。

确定dp数组含义：这个问题的环境不难想出dpSell[i]为前i天不持股(已经卖出)买卖股票获得的最大利润。

确定递推式：思考hold[i]和前面数据关系，因为只能买卖一次所以这个持有仅有后面被使用有效，一旦有更低的价格就更新所以hold[i]=max(hold[i-1],-prices[i])。

思考dpSell[i]和前面数据的关系，假设知道前i-1天的所有最大利润值，那么第i天获得最大利润的情况有两种：

第一种情况是第i天什么也不做，其最大利润还是前i-1天的利润(这种情况一般来说第i天股票数据没那么亮眼),此时dpSell[i]=dpSell[i-1]；第二种情况是第i天刚好卖了股票赚的利润是前i天获得的最大利润，此时需要在前i-1天手头有一支股票(并且是出现的价格最低的)才行即dpSell[i]=hold[i-1]+prices[i]。

在这个关系中，不持有股票dpSell[]是跟持有股票hold[]有关系,但是hold[]持有股票是相对独立，我们可以先看持有股票的情况，然后在此基础上分析不持有股票dpSell[],通过下面案例你可以更好的理解这其中的关系：

初始化dp数组：考虑0号位置、边缘位置以及特殊情况的一些值。这里根据递推式和实际知道只需要考虑0号位置的情况，第0天时候如果要持有只能买当天股票那么hold[0]=-prices[0]，但是第0天不持有股票最大利润只能为0(不买)。

那么完整的状态转移方程为：

hold[i]=max(hold[i-1],-prices[i]) //i>=1 以前就有最低的  或者以前不持 今天才持最低的
dpSell[i]=max(dpSell[i-1],hold[i-1]+prices[i])//i>=1 今天不卖最高利润和前面一样 或者今天卖了才获得最高利润
hold[0]=-prices[0]
dpSell[0]=0

确定遍历顺序：只需要初始0号位置，从1到最后顺序进行dp递推即可。

具体实现的代码为：

public int maxProfit (int[] prices) {// write code hereint hold[]=new int[prices.length];//持有int dpSell[]=new int[prices.length];//不持有hold[0]=-prices[0];//第0 必须买 这里用负数 后面直接max比较即可dpSell[0]=0;for(int i=1;i<prices.length;i++){//持有的最大(负数其实是最便宜的) 要么前面的最便宜的 要么今天的hold[i]=Math.max(hold[i-1],-prices[i]);//不持有股票的最大利润，要么前面利润就挺大，要么今天股票价格很高和昨天持有差利润更大dpSell[i]=Math.max(dpSell[i-1],prices[i]+hold[i-1]);}return dpSell[prices.length-1];
}

时间复杂度：O(n)，空间复杂度：O(n)。

买卖股票的最好时机(二)

题意

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
如果不能获取收益，请返回0
假设买入卖出均无手续费

分析

这个拓展和前面问题一是有区别的，区别就是可以多次买卖股票(就是这点区别需要我们思考)，但是同样每个时间段手中只能握着一支股票。

如果不用动态规划的思想，其实每次就比较相邻的两个决定是否买卖也能解决这个问题，但这里我们要用动态规划的思维去解决这个问题，有了上面一题的经验，相比这题解决起来并不是特别困难，套路也是差不多的。

确定dp数组含义：同上一样，我们用hold[]表示持有股票，dpSell[]表示不持有股票,hold[i]表示到第i天持有股票的最大利润,dpSell[i]为到第i天不持股(已经卖出)买卖股票获得的最大利润。

确定递推式：思考hold[i]和前面数据关系，持股的最大利润要么不变和前i-1天一样，要么就是第i天持有股票，那么需要拿前i-1天不持有股票的最大利润加上今天的股票价格，即hold[i]=max(hold[i-1],dpSell[i-1]-prices[i]),这里注意hold[i]不一定是负数，因为有可能前面的已经赚了很多导致hold[]变大。

思考dpSell[i]和前面数据的关系，假设知道前i-1天的所有最大利润值，那么第i天获得最大利润的情况有两种：

第一种情况是第i天什么也不做，此时dpSell[i]=dpSell[i-1]；第二种情况是第i天刚好卖了股票赚的利润是前i天获得的最大利润，此时需要在前i-1天手头有一支股票(并且是出现的价格最低的)才行即dpSell[i]=hold[i-1]+prices[i]。

初始化dp数组：这里初始化只需要考虑0号位置的持有hold[0]=-prices[0];表示初始状态需要持有的时候必须购买。

那么完整的状态转移方程为：

hold[i]=max(hold[i-1],dpSell[i-1]-prices[i]) //i>=1
dpSell[i]=max(dpSell[i-1],hold[i-1]+prices[i])// i>=1
hold[0]=-prices[0]
dpSell[0]=0

确定遍历顺序：从1到最后顺序进行dp递推即可。

具体实现代码为：

public int maxProfit(int[] prices) {int hold[]=new int[prices.length];//持有int dpSell[]=new int[prices.length];//不持有hold[0]=-prices[0];//初始化 持有只能买dpSell[0]=0;for(int i=1;i<prices.length;i++){//持有最大 要么前一个i-1最大，要么前一个不持股最大买第i个hold[i]=Math.max(hold[i-1],dpSell[i-1]-prices[i]);//不持股最大 要么前一个i-最大，要么前一个i-1持有最大然后第i天卖了dpSell[i]=Math.max(dpSell[i-1],prices[i]+hold[i-1]);} return dpSell[prices.length-1];
}

时间复杂度：O(n)，空间复杂度：O(n)。

买卖股票含冷冻期

描述

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

分析

这个问题和前一个问题很相似，就不详细展开详细讲解，我们考虑一下冷冻期对谁影响了就可以。

递推分析：我们考虑持有和不持有两个递推式有什么变化：

hold[i]第i天持有股票的最大值，第一种可能不做事继承前一天hold[i-1]是完全有可能的，第二种情况就是我想今天买入，但是卖出的话第二天无法买入有一天冷冻期，所以想今天(第i天)买入只能在第i-2天卖出不持有，然后第i-1天为冷冻期，今天第i天才能买入。

dpSell[i]第i天不持有股票的最大值，第一种可能不做事继承前一天dpSell[i-1]是完全有可能的，第二种情况就是我想今天卖出，那么前一天买第二天卖是可行的(不受冷冻期影响，冷冻只会冻结卖后的一天不能买)，所以第二种可能就是前一天第i-1天持有的最大然后今日卖出加上prices[i]。

那么递推式：

hold[i]=max(hold[i-1],dpSell[i-2]-prices[i]);
dpSell[i]=max(dpSell[i-1],hold[i-1]+prices[i]);

初始化考虑：根据递推式知道买入时候可能和前面两个数据有关系，所以我们需要初始0、1两个位置的数据，hold[0]=-prices[0]表示当天持有必买第0天，而hold[1]=max(-prices[0],-prices[1]);则是选择两天比较低的股价(因为这时候不会产生卖出的利润)。dpSell[0]=0表示最大利润为0，dpSell[1]=max(0,hold[0]+prices[1])表示最大要么是0，要么是昨天买今天卖。

确定遍历顺序：初始0,1号位置数据，从2开始遍历到最后递推即可。

具体实现代码为：

public int maxProfit(int[] prices) {if(prices.length<=1)return 0;int hold[]=new int[prices.length];int dpSell[]=new int[prices.length];hold[0]=-prices[0];hold[1]=Math.max(-prices[0],-prices[1]);dpSell[1]=Math.max(dpSell[0],hold[0]+prices[1]);for(int i=2;i<prices.length;i++){hold[i]=Math.max(hold[i-1],dpSell[i-2]-prices[i]);dpSell[i]=Math.max(dpSell[i-1],hold[i-1]+prices[i]);}return dpSell[prices.length-1];
}

时间复杂度：O(n)，空间复杂度：O(n)。

买卖股票的最佳时机含手续费

描述

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

分析

有了前面解决问题的基础，这个问题也不难解决了，其实这个问题和无限次购买区别不大，只是每次购买都有手续费。分析一下持有和不持有两种状态推导：

hold[i]继承前一天，或者前一天不持有最大减去今日股价，递推方式没变化。

dpSell[i]继承前一天，或者前一天持有最大加上今日股价，再加上fee的手续费，递推变化一点点。

递推式为：

hold[i]=max(hold[i-1],dpSell[i-1]-prices[i]);
dpSell[i]=max(dpSell[i-1],hold[i-1]+prices[i]-fee);

具体实现代码为：

public int maxProfit(int[] prices, int fee) {int hold[]=new int[prices.length];int dpSell[]=new int[prices.length];hold[0]=-prices[0];for(int i=1;i<prices.length;i++){hold[i]=Math.max(hold[i-1],dpSell[i-1]-prices[i]);dpSell[i]=Math.max(dpSell[i-1],hold[i-1]+prices[i]-fee);}return dpSell[prices.length-1];
}

时间复杂度：O(n)，空间复杂度：O(n)。

买卖股票的最好时机(三)

描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
如果不能获取收益，请返回0
假设买入卖出均无手续费

分析

其实这个问题比起上面就难一些，这里面提供两个思考的角度。

方法一：左右两个方向dp

前面我们解决过只能买卖一次的动态规划思路解决这个问题，但是股票买卖获取利润的实质是：低买高卖。

一般来说是从左向右进行枚举，但是想一下从右向左可以不？当然可以啊，从左向右就是记录一个最低价的股票与枚举值进行差值计算利润。而从右向左同样记录最大值然后向左枚举计算差值可以算出从右向左这个区间的最大利润。

知道从左向右和由右向左两个方向，有什么作用呢？两次买卖股票，对应两个区间一个左侧一个右侧，那么我们分别计算从左向右的买一次最大利润和从右向左计算买入一次的最大利润，然后每个位置dpLeft[i]和dpRight[i]值相加得到一个最大的即可！

public int maxProfit(int[] prices) {int dpleft[]=new int[prices.length];//从左向右的最大利润int dpright[]=new int[prices.length+1];//从右向左的最大利润if(prices.length<2)return  0;int value=0;//记录最大的那个int low=prices[0];for(int i=1;i<prices.length;i++){dpleft[i]=dpleft[i-1];//先继承左侧，然后判断买卖是否能够获得更大利润if(prices[i]<low) {//看看能否更新买入的最低值low = prices[i];continue;}int num=prices[i]-low;//看看dp值有没有更新if(num>dpleft[i-1]) {dpleft[i] =num;}}int high=prices[prices.length-1];for(int i=prices.length-2;i>=0;i--){dpright[i]=dpright[i+1];if(prices[i]>high){high=prices[i];continue;}int num=high-prices[i];//看看dp值有没有更新if(num>dpright[i+1]){dpright[i]=num;}}for(int i=1;i<prices.length;i++){int money=dpleft[i]+dpright[i];if(money>value)value=money;}return  value;
}

时间复杂度：O(n)，空间复杂度：O(n)。

法二：顺序两次dp

上面方法属于一个小技巧，但是这个问题如果常规的从左向右正常思维解决该如何处理呢？

确定dp数组含义：我们分析一下这个过程，正常买卖两次股票有四个步骤同时也对应四个数组：第一次(买入)持有hold1[]，第一次(卖出)不持有dpSell1[]，第二次(买入)持有hold2[]，第二次(卖出)不持有dpSell2[]。

确定递推式：我们需要分析这些数据有什么关系，我们根据前面的问题很清楚hold1和dpSell1是有关系的，在这里我把他们的关系再给大家梳理一遍：

第一次买入hold1[i]:要么和第i-1天第一次持有的最大利润相同，要么就是-prices[i]第一次持有最大利润，即hold1[i]=max(hold[i-1],-prices[i])。
第一次不持有dpSell1[i]：要么和第i-1天第一次不持有dpSell1[i]相同，要么和第i-1天第一次持有利润加上第i天价格(卖出)，即dpSell1[i]=max(dpSell[i-1],hold1[i-1]+price[i])。
第二次持有hold2[i]:要么和i-1天第二次持有的最大利润相同，要么就是第i-1天第一次不持有的最大利润减去prices[i],即要么不动跟昨天一样，要么就是昨天第一次不持有(昨天已经买卖第一次)然后今天再买入时候最大，即hold2[i]=max(hold2[i-1],dpSell1[i-1]-prices[i])。
第二次不持有dpSell2[i]:要么和第i-1天第二次不持有最大利润相同，要么和第i-1天第二次持有利润加上第i天价格(卖出)，即mdpSell2[i]=ax(dpSell2[i-1],hold2[i-1]+prices[i])。

初始化dp数组：hold1[0]=hold2[0]=-prices[0]，即第一次第二次买入时候均购买第0天价格股票。

确定遍历顺序：只需要初始0号位置，从1开始顺序枚举同时进行第一次第二次的动态规划递推。

实现的代码为：

public int maxProfit (int[] prices) {// write code hereint hold1[]=new int[prices.length];//第一次持有int dpSell1[]=new int[prices.length];//第一次不持有int hold2[]=new int[prices.length];//第二次持有int dpSell2[]=new int[prices.length];//第二次不持有hold1[0]=hold2[0]=-prices[0];for(int i=1;i<prices.length;i++){hold1[i]=Math.max(hold1[i-1],-prices[i]);dpSell1[i]=Math.max(dpSell1[i-1],prices[i]+hold1[i-1]);hold2[i]=Math.max(hold2[i-1],dpSell1[i-1]-prices[i]);dpSell2[i]=Math.max(dpSell2[i-1],hold2[i-1]+prices[i]);}return dpSell2[prices.length-1];
}

时间复杂度：O(n)，空间复杂度：O(n)。

买卖股票的最好时机(四)

描述

1 你最多可以对该股票有k笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2 如果不能获取收益，请返回0
3 假设买入卖出均无手续费

分析

这个问题和买卖股票的最好时机(三)有些相似，但是是它的变形题。相信到这里，你对持有股票hold、不持有股票dpSell的最大利润的概念已经理解的很透彻了。咱们前面的问题都是主要在搞明白持有股票hold、不持有股票dpSell最大利润之间以及天数i的联系。

我们简单回顾一下前面的股票问题主要的状态转移方程：

股票问题(一)：只能购买一次,持有可以继承前一天或者选今天最低-prices[i](本来是0持有后花钱就变成负的了)，不持有可以继承前一天最低或计算今天出售利润选择高的那个。

hold[i]=max(hold[i-1],-prices[i]) 
dpSell[i]=max(dpSell[i-1],hold[i-1]+prices[i])

股票问题(二)：可购买股票多次，这时候不持有dpSell[i]和买卖股票(一)其实是没区别的，要么继承前一天，要么今日股价加上截止昨日不持有的最大利润；

但是持有股票hold[i]的最大利润计算方式有所变化，这里面允许多次交易，那么持有最大的利润就是前一天不持有的最大利润dpSell[i-1]加上今天的股价(即今天卖出)或者今天不动继承昨天的最大利润。股票(一)受到只能买一次影响所以不能使用前一天不持有d最大利润来计算。

hold[i]=max(hold[i-1],dpSell[i-1]-prices[i]) 
dpSell[i]=max(dpSell[i-1],hold[i-1]+prices[i])

股票问题(三)：可以购买两次，这个和只能买一次和购买任意次又有所区别，但是前面也分析过购买一次(hold1[i]、dpSell1[i])是和前面股票(一)是一样处理。

但是购买第二次的问题考虑是在购买第一次的基础上的。第二次持有hold2[i]要么继承前一天要么是前一天第一次不持有(dpSell1[i])然后今日购买；第二次不持有dpSell2[i]要么继承前一天要么是前一天第二次持有最大加上今日股价(今天卖掉)。

hold1[i]=max(hold1[i-1],-prices[i]);
dpSell1[i]=max(dpSell1[i-1],hold1[i-1]+prices[i]);hold2[i]=max(hold2[i-1],dpSell1[i-1]-prices[i]);
dpSell2[i]=max(dpSell2[i-1],hold2[i-1]+prices[i]);

其实这个问题和股票(三)问题很相似，股票一二是弄明白股票利润与天数的关系，股票三是弄明白两次买卖股票的关系，而这个问题允许买卖K次股票(同时手中只允许有一支股票)，我们来详细分析一下这个问题：

确定dp数组含义：股票三买卖两次我们创建了两对数组，这个k次当然要提高维度来解决，创建hold[prices.length][k+1]、dpSell[prices.length][k+1]，其中hold[i][j+1]表示第i天第j次持有股票的最大利润，dpSell[i][j+1]表示第i天第j次不持有股票的最大利润，至于为什么设置成k+1后面再说明。

确定递推式：我们要分析hold[i][j]和dpSell[i][j]和前面数据之间的关系。

hold[i][j]：到第i天第j次持有，它的值可能是前一天(i-1)持有j次最大值hold[i-1][j]，另外一个可能情况是前一天(i-1)的第j-1次不持有最大然后买入今日股票(昨天刚卖了，然后今天买入)，即dpSell[i-1][j-1]-prices[i]。

dpSell[i][j]：到第i天第j次不持有,它的值可能是前一天(i-1)不持有j次最大值dpSell[i-1][j]，还有可能是前一天(i-1)的第j次持有最大然后卖出今日股票(昨天的第j次买入最大，然后今天卖了)，即hold[i-1][j]+prices[i]。

这个持有和不持有对应的其实是这么一个二维结构：

总结一下除了继承前一天的持有或者不持有之外：

hold持有：前一天(i-1)的上次(j-1)不持有减去今日股价。(前一次不持有买卖结束了，再买就是下一次)

dpSell不持有：前一天(i-1)的这次(j)持有加上今日股价。(前一次持有，说明还没卖出去，那么这一次j还没结束，自己计算完才算结束)

完整递推式为：

hold[i][j]=max(hold[i-1][j],dpSell[i-1][j-1]-prices[i]);//前一天同次数 或者前一天不持有上一次的 今天买
dpSell[i][j]=max(dpSell[i-1][j],hold[i-1][j]+prices[i]);//前一天同次数 或者前一天持有的通次 今天卖

初始化dp数组：根据前面递推，和前面初始化，我们知道第0天持有必须购买prices[0]的股票，所以不管第0天的第几次持有dp[0][j]=0，但是上面根据公式知道第j次可能会用到j-1，这里j是我们新定义的一个含义变量，我们让它从1开始计数，让0号位置的数据能够满足初始递推成功进行即可，就不用考虑j初始的特殊情况了，所以前面的k+1是这么来的。

确定遍历顺序：外层i从1开始到prices.length-1枚举里面处理第i天的持有和不持股票有最大利润，内层j从1到k表示表示计算这第i天第j次购买的最大利润(i天数从0开始有效计数，j次数从1开始有效计数)。

具体实现代码为：

public int maxProfit(int k, int[] prices) {if(prices.length==0)return 0;int hold[][]=new int[prices.length][k+1];int dpSell[][]=new int[prices.length][k+1];for(int i=1;i<k+1;i++){hold[0][i]=-prices[0];}hold[0][0]=-prices[0];for(int i=1;i<prices.length;i++){for(int j=1;j<k+1;j++){hold[i][j]=Math.max(hold[i-1][j],dpSell[i-1][j-1]-prices[i]);dpSell[i][j]=Math.max(dpSell[i-1][j],hold[i-1][j]+prices[i]);}}//System.out.println(Arrays.deepToString(dpSell));return dpSell[prices.length-1][k];}