题目：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
题解：
前面我们一起学习了买卖股票1、2的算法，分别对应只能交易1次，可以无限次交易的最大利润。但是该题最多交易2次（可以交易0次、1次、2次），此时的情况就有点复杂了，这时候就不能用贪心思想来解决了，要用动态规划算法了。
动态规划解题的2个步骤：
1.状态定义
对于股票的状态有2种，持有、不持有。即买入和卖出。
2.状态转移方程
此题的状态转移方程有点复杂，中等难度的动态规划题目的记忆数组memo（即dp数组）一般是一维、二维数组，但是此题要用到三维数组。这也是为什么此题是一道困难题目的原因。转移方程如下：
记忆三维数组 memo定义：memo[天数][是否持有股票][卖出次数]
memo[i][0][0] = memo[i-1][0][0];//什么也不做 //未持股但卖出了1次 memo[i][0][1] = Math.max(memo[i-1][0][1],memo[i-1][1][0] + prices[i]); //未持股但卖出了2次 memo[i][0][2] = Math.max(memo[i-1][0][2], memo[i-1][1][1] + prices[i]); //持股并且卖出了0次 memo[i][1][0] = Math.max(memo[i-1][1][0], memo[i-1][0][0] - prices[i]); //持股并且卖出了1次 memo[i][1][1] = Math.max(memo[i-1][1][1], memo[i-1][0][1] - prices[i]); //持股并且卖出了1次,此情况不会存在 memo[i][1][2] = Integer.MIN_VALUE / 2;
下面直接上代码：
解法1：三维数组memo
public int maxProfit(int[] prices) { if(prices == null || prices.length < 2) return 0; int len = prices.length; //三维数组 memo[天数][是否持有股票][卖出次数] int[][][] memo = new int[len][2][3]; memo[0][0][0] = 0;//0次交易后不持有股票的利润 memo[0][0][1] = Integer.MIN_VALUE/2 ;//此情况不存在,除以2防止越界 memo[0][1][0] = -prices[0];; memo[0][1][1] = Integer.MIN_VALUE/2;//此情况不存在 memo[0][1][2] = Integer.MIN_VALUE/2;//此情况不存在 //memo[0][2][1] = -prices[0]; for(int i=1;i<len;i++){ memo[i][0][0] = memo[i-1][0][0];//什么也不做 //未持股但卖出了1次 memo[i][0][1] = Math.max(memo[i-1][0][1],memo[i-1][1][0] + prices[i]); //未持股但卖出了2次 memo[i][0][2] = Math.max(memo[i-1][0][2], memo[i-1][1][1] + prices[i]); //持股并且卖出了0次 memo[i][1][0] = Math.max(memo[i-1][1][0], memo[i-1][0][0] - prices[i]); //持股并且卖出了1次 memo[i][1][1] = Math.max(memo[i-1][1][1], memo[i-1][0][1] - prices[i]); //持股并且卖出了1次,此情况不会存在 memo[i][1][2] = Integer.MIN_VALUE / 2; } //未持股时利润才会更大 int a = Math.max(memo[len-1][0][0] , memo[len-1][0][1]); int b = Math.max(a,memo[len-1][0][2]); return Math.max(b, 0); }
解法2：二维数组（三维数组的空间优化版）
public int maxProfit(int[] prices) { if(prices == null || prices.length < 2) return 0; int len = prices.length; //二维数组 memo[天数][状态] int[][] memo= new int[len][5]; //0 未持股但卖出了0次(什么也不做),1 未持股但卖出了1次,2 未持股但卖出了2次, 3 持股并且卖出了0次,4 持股并且卖出了1次 //第一天 memo[0][0] = 0; memo[0][1] = Integer.MIN_VALUE /2;//此情况不存在,除以2防止越界 memo[0][2] = Integer.MIN_VALUE / 2;//此情况不存在,除以2防止越界 memo[0][3] = -prices[0]; memo[0][4] = Integer.MIN_VALUE / 2;//此情况不存在,除以2防止越界 for(int i=1;i<len;i++){ //未持股但卖出了0次 memo[i][0] = memo[i-1][0];//什么也不做,不买也不卖 //未持股但卖出了1次 memo[i][1] = Math.max(memo[i-1][1],memo[i-1][3] + prices[i]); //未持股但卖出了2次 memo[i][2] = Math.max(memo[i-1][2], memo[i-1][4] + prices[i]); //持股并且卖出了0次 memo[i][3] = Math.max(memo[i-1][3], memo[i-1][0] - prices[i]); //持股并且卖出了1次 memo[i][4] = Math.max(memo[i-1][4], memo[i-1][1] - prices[i]); } //未持股时利润才会更大 int a = Math.max(memo[len-1][0] , memo[len-1][1]); int b = Math.max(a,memo[len-1][2]); return Math.max(b, 0); }
解法3：终极空间优化版，该解法不好理解，建议先把解法1，解法2理解后再来看这个解法。
Java版本：
public int maxProfit(int[] prices) { /** 对于任意一天考虑四个变量: fstBuy: 在该天第一次买入股票可获得的最大收益 fstSell: 在该天第一次卖出股票可获得的最大收益 secBuy: 在该天第二次买入股票可获得的最大收益 secSell: 在该天第二次卖出股票可获得的最大收益 分别对四个变量进行相应的更新, 最后secSell就是最大 收益值(secSell >= fstSell) **/ int fstBuy = Integer.MIN_VALUE, fstSell = 0; int secBuy = Integer.MIN_VALUE, secSell = 0; for(int p : prices) { fstBuy = Math.max(fstBuy, -p); fstSell = Math.max(fstSell, fstBuy + p); secBuy = Math.max(secBuy, fstSell - p); secSell = Math.max(secSell, secBuy + p); } return secSell; }
JS版本：
var maxProfit = function(prices) { //动态规划 if(prices == null || prices.length == 1) return 0; /** 对于任意一天考虑四个变量: fstBuy: 在该天第一次买入股票可获得的最大收益 fstSell: 在该天第一次卖出股票可获得的最大收益 secBuy: 在该天第二次买入股票可获得的最大收益 secSell: 在该天第二次卖出股票可获得的最大收益 分别对四个变量进行相应的更新, 最后secSell就是最大 收益值(secSell >= fstSell) **/ let fstBuy = -Infinity, fstSell = 0; let secBuy = -Infinity, secSell = 0; for(let p of prices) { fstBuy = Math.max(fstBuy, -p); fstSell = Math.max(fstSell, fstBuy + p); secBuy = Math.max(secBuy, fstSell - p); secSell = Math.max(secSell, secBuy + p); } return secSell; };