123. Best Time to Buy and Sell Stock III 发表于 2022-02-16 12345678910111213141516171819202122232425262728class Solution { public int maxProfit(int[] prices) { int n = prices.length; // 定义 dp[i][j] 表示第 i 天休市时处于 j 状态的最大利润 // j = 0: 未购买过 // j = 1: 买入一次 // j = 2: 买入、卖出 // j = 3: 买入、卖出、买入 // j = 4: 买入、卖出、买入、卖出 int[][] dp = new int[n][5]; dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0; dp[0][3] = -prices[0]; dp[0][4] = 0; for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][0]; dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - 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[n - 1][4]; // 因为同一天可以买卖多次,所以最大值一定能转移到该状态 }} Reference123. Best Time to Buy and Sell Stock III