leetcode hot100 买卖股票最佳时机3
本题中，依旧可以采用动态规划来进行解决，之前的两个题我们都是用二维数组dp[i][2]来表示的，其中i表示第i天，2表示长度为2，其中0表示不持有，1表示持有。
本题中，说至多完成两笔交易，也就是说我们可以买卖1次或者两次，然后获取价格最大的交易即可。所以说我们也还是要区分状态，只不过这次状态需要区分第一次第二次。
dp[i][0]表示不操作，dp[i][1]表示在第i天第一次持有，dp[i][2]表示在第i天第一次不持有，dp[i][3]表示第i天第二次持有，dp[i][4]表示在第i天第二次不持有。
所以 递推公式如下
dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
dp[i][1]表示第i天第一次持有，可能是前一天就已经持有了，也可能是前一天没持有，然后当天第1次买入（第一次买入所以是-prices[i]）。
dp[i][2]表示第i天第一次不持有，可能是前一天就已经不持有了，也可能是前一天持有，然后第i天卖出了。
dp[i][3]表示第i天第二次持有，可能是前一天就已经是第二次持有了，也可能前一天第1次不持有，然后第i天买入
dp[i][4]表示第i天第二次不持有，可能是前一天就第二次不持有了，也可能是前一天第二次持有，然后第i天卖出。
初始化：
dp[0][0]表示第0天没有操作，所以是0
dp[0][1]表示第0天，第一次持有，是-prices[0]
dp[0][2]表示第0天，第一次不持有，则是当天买然后当天卖 所以是0
dp[0][3]表示第0天，第二次持有，也就是第一次买完然后卖掉，再买，就是-prices[0]
dp[0][4]表示第0天，第二次不持有，就是第一次买完卖掉，当天再买再卖，所以是0
遍历顺序：
由前一天推出后一天的状态，所以应该是从前往后遍历
打印数组：我们最后打印的，一定是卖出股票的钱，所以就是dp[len-1][2]和dp[len-1][4]的最大值。
// 版本一
class Solution {public int maxProfit(int[] prices) {int len = prices.length;// 边界判断, 题目中 length >= 1, 所以可省去if (prices.length == 0) return 0;/** 定义 5 种状态:* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出*/int[][] dp = new int[len][5];dp[0][1] = -prices[0];// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润dp[0][3] = -prices[0];for (int i = 1; i < len; i++) {dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[len - 1][4];}
}