程序人生|漫画：程序教你寻找股票买入卖出的最佳时机（动态规划）( 四 )

本文插图
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== || 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 for(int j=1;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]; }

本文插图

本文插图

本文插图

本文插图

本文插图