day113（3.15）——leetcode面试经典150

123. 买卖股票的最佳时机 III

123. 买卖股票的最佳时机 Ⅲ

题目：

题解：

class Solution { // 可以买卖多次，但手里只能持有一股。 // 最多可以完成 两笔 交易。 // 因为可以多次买卖，所以“买入”的时候，可以用“上一次卖出赚的钱”来抵扣成本。 public int maxProfit(int[] prices) { //如果当前股票的数量<2,直接就是不持有股票，利润为0 if(prices==null||prices.length<2) { return 0; } int n = prices.length; int[][] dp = new int[n][4]; //创建二维数组 //int[i][0]: 第1次卖入后的最大收益 //表示第i天没有股票，（可能之前有，但就在第i天卖掉了，也可能之前就没有，所以第i天也不买） dp[0][0]=0; //int[i][1]: 第1次买入后的最大收益 //表示第i天有股票，（可能之前有，但第i天也不买，也可能之前就没有，所以第i天就买了） dp[0][1]=-prices[0]; // dp[i][2]: 第2次卖入后的最大收益 //表示第i天没有股票，买了->卖了->又买->卖了 dp[0][2]=0; // dp[i][3]: 第2次买出后的最大收益 //表示第i天有股票，买了->卖了->又买 dp[0][3]=-prices[0]; //遍历每一天的股票数 for(int i=1;i<n;i++) { //dp[i][0]状态：要么之前卖的，要么今天卖（用第一次买入的状态 + 今天价格） dp[i][0] = Math.max(prices[i]+dp[i-1][1], dp[i-1][0]); //dp[i][1]状态：要么之前买的，要么今天刚买（初始资金0） dp[i][1] = Math.max(dp[i-1][1], -prices[i]); //dp[i][2]状态：要么之前卖的，要么今天卖（用第二次买入的状态 + 今天价格） dp[i][2] = Math.max(prices[i]+dp[i-1][3], dp[i-1][2]); //dp[i][3]状态：要么之前买的，要么今天刚买（用第一次卖出的利润 - 今天价格） dp[i][3] = Math.max(dp[i-1][0]-prices[i], dp[i-1][3]); } //一定是没有股票的时候能得到最大利润，如果当前有股票，那一定是亏钱的，且肯定是进行完了第二次交易后最大 return dp[n-1][2]; } }