前一段时间，小灰发布了上下两篇关于股票买卖的算法题讲解，激发了很多小伙伴的兴趣。
这一次，小灰把这两篇漫画整合在一起，并且修改了其中的一些细节错误，感谢小伙伴们的指正。
————— 第二天 —————
什么意思呢？让我们来举个例子，给定如下数组：
该数组对应的股票涨跌曲线如下：
显然，从第2天价格为1的时候买入，从第5天价格为8的时候卖出，可以获得最大收益：
此时的最大收益是 8-1=7。
在上面这个例子中，最大值9在最小值1的前面，我们又该怎么交易？总不能让时间倒流吧？
————————————
以下图为例，假如我们已经确定价格4的时候为卖出时间点，那么此时最佳的买入时间点是哪一个呢？
我们要选择价格4之前的区间，且必须是区间内最小值，显然，这个最佳的选择是价格2的时间点。
第1步，初始化操作，把数组的第1个元素当做临时的最小价格；最大收益的初始值是0：
第2步，遍历到第2个元素，由于2
第3步，遍历到第3个元素，由于7>2，所以当前的最小价格仍然是2；如我们刚才所讲，假设价格7为卖出点，对应的最佳买入点是价格2，两者差值7-2=5，5>0，所以当前的最大收益变成了5：
第4步，遍历到第4个元素，由于4>2，所以当前的最小价格仍然是2；4-2=2，2
第5步，遍历到第5个元素，由于3>2，所以当前的最小价格仍然是2；3-2=1，1
以此类推，我们一直遍历到数组末尾，此时的最小价格是1；最大收益是8-1=7：
public class StockProfit { public static int maxProfitFor1Time(int prices[]) { if(prices==null || prices.length==0) { return 0; } int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.length; i ) { if (prices[i] maxProfit){ maxProfit = prices[i] – minPrice; } } return maxProfit; } public static void main(String[] args) { int[] prices = {9,2,7,4,3,1,8,4}; System.out.println(maxProfitFor1Time(prices)); }}
我们以下图这个数组为例，直观地看一下买入卖出的时机：
在图中，绿色的线段代表价格上涨的阶段。既然买卖次数不限，那么我们完全可以在每一次低点都进行买入，在每一次高点都进行卖出。
这样一来，所有绿色的部分都是我们的收益，最大总收益就是这些局部收益的加总：
（6-1） （8-3） （4-2） （7-4） = 15
至于如何判断出这些绿色上涨阶段呢？很简单，我们遍历整个数组，但凡后一个元素大于前一个元素，就代表股价处于上涨阶段。
public int maxProfitForAnyTime(int[] prices) { int maxProfit = 0; for (int i = 1; i prices[i-1]) maxProfit = prices[i] – prices[i-1]; } return maxProfit; }
我们仍然以之前的数组为例：
首先，寻找到1次买卖限制下的最佳买入卖出点：
两次买卖的位置是不可能交叉的，所以我们找到第1次买卖位置后，把这一对买入卖出点以及它们中间的元素全部剔除掉：
接下来，我们按照同样的思路，再从剩下的元素中寻找第2次买卖的最佳买入卖出点：
这样一来，我们就找到了最多2次买卖情况下的最佳选择：
对于上图的这个数组，如果独立两次求解，得到的最佳买入卖出点分别是【1,9】和【6,7】，最大收益是 （9-1） （7-6）=9：
但实际上，如果选择【1,8】和【3,9】，最大收益是（8-1） （9-3）=13>9：
当第1次最佳买入卖出点确定下来，第2次买入卖出点的位置会有哪几种情况呢？
情况1：第2次最佳买入卖出点，在第1次买入卖出点左侧
情况2：第2次最佳买入卖出点，在第1次买入卖出点右侧
情况3：第1次买入卖出区间从中间截断，重新拆分成两次买卖
那么，如何判断给定的股价数组属于那种情况呢？很简单，在第1次最大买入卖出点确定后，我们可以比较一下哪种情况带来的收益增量最大：
寻找左侧和右侧的最大涨幅比较好理解，寻找中间的最大跌幅有什么用呢？
细想一下就能知道，当第1次买卖需要被拆分开来的时候，买卖区间内的最大跌幅，就等同于拆分后的收益增量（类似于炒股的抄底操作）：
这样一来，我们可以总结出下面的公式：
最大总收益 = 第1次最大收益 Max（左侧最大涨幅，中间最大跌幅，右侧最大涨幅）
所谓动态规划，就是把复杂的问题简化成规模较小的子问题，再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解。
首先，让我们分析一下当前这个股票买卖问题，这个问题要求解的是一定天数范围内、一定交易次数限制下的最大收益。
既然限制了股票最多买卖2次，那么股票的交易可以划分为5个阶段：
没有买卖
第1次买入
第1次卖出
第2次买入
第2次卖出
我们把股票的交易阶段设为变量m（用从0到4的数值表示），把天数范围设为变量n。而我们求解的最大收益，受这两个变量影响，用函数表示如下：
最大收益 = F（n，m）（n>=1，0
既然函数和变量已经确定，接下来我们就要确定动态规划的两大要素：
1.问题的初始状态2.问题的状态转移方程式
问题的初始状态是什么呢？我们假定交易天数的范围只限于第1天，也就是n=1的情况：
1.如果没有买卖，也就是m=0时，最大收益显然是0，也就是 F（1,0）= 0
2.如果有1次买入，也就是m=1时，相当于凭空减去了第1天的股价，最大收益是负的当天股价，也就是 F（1,1）= -price[0]
3.如果有1次买出，也就是m=2时，买卖抵消（当然，这没有实际意义），最大收益是0，也就是 F（1,2）= 0
4.如果有2次买入，也就是m=3时，同m=1的情况，F（1,3）= -price[0]
5.如果有2次卖出，也就是m=4时，同m=2的情况，F（1,4）= 0
确定了初始状态，我们再来看一看状态转移。假如天数范围限制从n-1天增加到n天，那么最大收益会有怎样的变化呢？
这取决于现在处于什么阶段（是第几次买入卖出），以及对第n天股价的操作（买入、卖出或观望）。让我们对各个阶段情况进行分析：
1.假如之前没有任何买卖，而第n天仍然观望，那么最大收益仍然是0，即 F（n，0） = 0
2.假如之前没有任何买卖，而第n天进行了买入，那么最大收益是负的当天股价，即 F（n，1）= -price[n-1]
3.假如之前有1次买入，而第n天选择观望，那么最大收益和之前一样，即 F（n，1）= F（n-1，1）
4.假如之前有1次买入，而第n天进行了卖出，那么最大收益是第1次买入的负收益加上当天股价，即那么 F（n，2）= F（n-1，1） price[n-1]
5.假如之前有1次卖出，而第n天选择观望，那么最大收益和之前一样，即 F（n，2）= F（n-1，2）
6.假如之前有1次卖出，而第n天进行2次买入，那么最大收益是第1次卖出收益减去当天股价，即F（n，3）= F（n-1，2） – price[n-1]
7.假如之前有2次买入，而第n天选择观望，那么最大收益和之前一样，即 F（n，3）= F（n-1，3）
8.假如之前有2次买入，而第n天进行了卖出，那么最大收益是第2次买入收益减去当天股价，即F（n，4）= F（n-1，3） price[n-1]
9.假如之前有2次卖出，而第n天选择观望（也只能观望了），那么最大收益和之前一样，即 F（n，4）= F（n-1，4）
最后，我们把情况【2，3】，【4，5】，【6、7】，【8，9】合并，可以总结成下面的5个方程式：
F（n，0） = 0
F（n，1）= max（-price[n-1]，F（n-1，1））
F（n，2）= max（F（n-1，1） price[n-1]，F（n-1，2））
F（n，3）= max（F（n-1，2）- price[n-1]，F（n-1，3））
F（n，4）= max（F（n-1，3） price[n-1]，F（n-1，4））
从后面4个方程式中，可以总结出每一个阶段最大收益和上一个阶段的关系：
F（n，m） = max（F（n-1，m-1） price[n-1]，F（n-1，m））
由此我们可以得出，完整的状态转移方程式如下：
在表格中，不同的行代表不同天数限制下的最大收益，不同的列代表不同买卖阶段的最大收益。
我们仍然利用之前例子当中的数组，以此为基础来填充表格：
首先，我们为表格填充初始状态：
接下来，我们开始填充第2行数据。
没有买卖时，最大收益一定为0，因此F（2,0）的结果是0：
根据之前的状态转移方程式，F（2,1）= max（F（1,0）-2，F（1,1））= max（-2，-1）= -1，所以第2行第2列的结果是-1：
F（2,2）= max（F（1,1） 2，F（1,2））= max（1，0）= 1，所以第2行第3列的结果是1：
F（2,3）= max（F（1,2）-2，F（1,3））= max（-2，-1）= -1，所以第2行第4列的结果是-1：
F（2,4）= max（F（1,3） 2，F（1,4））= max（1，0）= 1，所以第2行第5列的结果是1：
接下来我们继续根据状态转移方程式，填充第3行的数据：
接下来填充第4行：
以此类推，我们一直填充完整个表格：
如图所示，表格中最后一个数据13，就是全局的最大收益。
//最大买卖次数 private static int MAX_DEAL_TIMES = 2; public static int maxProfitFor2Time(int[] prices) { if(prices==null || prices.length==0) { return 0; } //表格的最大行数 int n = prices.length; //表格的最大列数 int m = MAX_DEAL_TIMES*2 1; //使用二维数组记录数据 int[][] resultTable = new int[n][m]; //填充初始状态 resultTable[0][1] = -prices[0]; resultTable[0][3] = -prices[0]; //自底向上，填充数据 for(int i=1;i<n; i) { for(int j=1;j<m;j ){ if((j&1) == 1){ resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-1]-prices[i]); }else { resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-1] prices[i]); } } } //返回最终结果 return resultTable[n-1][m-1]; }
//最大买卖次数 private static int MAX_DEAL_TIMES = 2; public static int maxProfitFor2TimeV2(int[] prices) { if(prices==null || prices.length==0) { return 0; } //表格的最大行数 int n = prices.length; //表格的最大列数 int m = MAX_DEAL_TIMES*2 1; //使用一维数组记录数据 int[] resultTable = new int[m]; //填充初始状态 resultTable[1] = -prices[0]; resultTable[3] = -prices[0]; //自底向上，填充数据 for(int i=1;i在这段代码中，resultTable从二维数组简化成了一维数组。由于最大买卖次数是常量，所以算法的空间复杂度也从O（n）降低到了O（1）。
public static int maxProfitForKTime(int[] prices, int k) { if(prices==null || prices.length==0 || k<=0) { return 0; } //表格的最大行数 int n = prices.length; //表格的最大列数 int m = k*2 1; //使用一维数组记录数据 int[] resultTable = new int[m]; //填充初始状态 for(int i=1;i<m;i =2) { resultTable[i] = -prices[0]; } //自底向上，填充数据 for(int i=1;i<n;i ) { for(int j=1;j<m;j ){ if((j&1) == 1){ resultTable[j] = Math.max(resultTable[j], resultTable[j-1]-prices[i]); }else { resultTable[j] = Math.max(resultTable[j], resultTable[j-1] prices[i]); } } } //返回最终结果 return resultTable[m-1]; }
喜欢本文的朋友，欢迎关注公众号 程序员小灰，收看更多精彩内容
股票什么时间买入什么时间卖出
股票买卖时间：开盘时、9:30～10:00、11点30分、14:00～14:30、14:50～15:00。买卖股票的最佳时间段如下：1）开盘建议进行第一次出货：开盘价一般受昨日收盘价影响。若昨日股指、股价以最高位报收，次日开盘往往跳空高开，即开盘股指、股价高一昨日收盘股指、股价;反之，若昨日股指、股价以最低报价，次日开盘价往往低开。2）9:30～10:00是第二次出入货时机：要出脱“热门股”，若股价开盘后高开高走，股价急剧上涨，最高价常出现于上午10:00以前，且成交量急剧放大，所以，10:00以前为“热门股”出货时机。3）11点30分是出入货第三次机会：“热门股”为出货信号，上午走势，随成交放大，一浪高于一浪，应立即出货。若“热门股”为炒作信号，可能以最高价收市。随成交量放大，一浪高于一浪，可考虑买入。4）14:00～14:30是第四次出货时机：此时是沪市的“平仓盘”时间，股指、股价往往出现当日最高价、次高价。5）14:50～15:00是全日最后一次买卖股票时机：收盘股指、股价也可能出现全日最高股指、股价。此时多方经一日稳步进攻，终于突破股指阻力位。拓展资料：1.股价走势有三种，在三种走势中，买点和卖点是不同的。1）一种走势是上升趋势，即均线系统向上，k线走势沿着均线系统振荡向上。这时的买点应该是股价调整到均线附近时（具体调到5日、10日、20日均线，要看具体的股票和k线走势），卖点应该是股价创出短期新高时（中长线持股和极端行情除外）。2）第二种走势横盘，即均线系统横着走，k线在一个箱体种上下振荡。这时的买点是股价调整到箱体的下轨时，卖点在上升到箱体的上轨时。3）第三种走势是下跌趋势，即均线系统向下，k线走势沿着均线系统振荡向下。这时最好不要操作，风险较大。
股票卖出的最佳时间点
股票最佳买卖时间：1.上午最佳卖出是早上开盘一冲高和11：00左右 (大盘高开10点前卖，低开等反弹在卖)。2.上午最佳买入是大盘低开和10：00-10：30分左右。3.下午最佳买入是2：00-2：30大家注意观察。4.下午最佳卖出是13：10分-13：30分。拓展资料：股票卖出的好时机：（一）大盘行情形成大头部时，坚决清仓全部卖出。上证指数或深综合指数大幅上扬后，形成中期大头部时，是卖出股票的关键时刻。不少市场评论认为抛开指数炒个股，这种提法不科学。只关注个股走势是只见树木不见森林。根据历史统计资料显示：大盘形成大头部下跌，竟有90%~95%以上的个股形成大头部下跌。大盘形成大底部时，有80%-90%以上的个股形成大底部。大盘与个股的联动性相当强，少数个股在主力介入操控下逆市上扬，这仅仅是少数、个别现象。要逮到这种逆市上扬的“庄股”概率极低，因此，大盘一旦形成大头部区，是果断分批卖出股票的关键时刻。（二）大幅上升后，成交量大幅放大，是卖出股票的关键。当股价大幅上扬之后，持股者普遍获利，一旦某天该股大幅上扬过程中出现卖单很大、很多，特别是主动性抛盘很大，反映主力、大户纷纷抛售，这是卖出的强烈信号。尽管此时买入的投资者仍多，买入仍踊跃，这很容易迷惑看盘经验差的投资者，有时甚至做出换庄的误判，其实主力是把筹码集中抛出，没有大主力愿在高价区来收集筹码，来实现少数投资者期盼的“换庄”目的。成交量创下近数个月甚至数年的最大值，是主力卖出的有力信号，是持股者卖出的关键，没有主力拉抬的股票难以上扬，仅靠广大中小散户很难推高股价的。上扬末期成交量创下天量，90%以上形成大头部区。（三）上升较大空间后，日K线出现十字星或长上影线的倒锤形阳线或阴线时，是卖出股票的关键。上升一段时间后，日K线出现十字星，反映买方与卖方力量相当，局面将由买方市场转为卖方市场，高位出现十字星犹如开车遇到十字路口的红灯，反映市场将发生转折。股价大幅上升后，出现带长影线的倒锤形阴线，反映当日抛售者多，若当日成交量很大，更是见顶信号。许多个股形成高位十字星或倒锤形长上影阴线时，80%-90%的机会形成大头部，是果断卖出关键。（四）股价大幅上扬后公布市场早已预期的利好消息是卖出的关键。（五）股价大幅上扬后，除权日前后是卖股票的关键时机。上市公司年终或中期实施送配方案，股价大幅上扬后，股权登记日前后或除权日前后，往往形成冲高出货的行情，一旦该日抛售股票连续出现十几万股的市况，应果断卖出，反映主力出货，不宜久持该股。
