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

image.png
image.png

动态规划

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  4.         /**dp[i][0] 没有操作
  5.          * dp[i][1] 第一次买入
  6.          * dp[i][2] 第一次卖出
  7.          * dp[i][3] 第二次买入
  8.          * dp[i][4] 第二次卖出
  9.          */
  11.         int size = prices.length;
  12.         int [][] dp = new int[size][5];
  14.         dp[0][0] = 0; 
  15.         dp[0][1] = -prices[0]; 
  16.         dp[0][2] = 0;
  17.         dp[0][3] = -prices[0];
  18.         dp[0][4] = 0;
  20.         for(int i = 1; i < size; i++ ) {
  21.             dp[i][0] = dp[i - 1][0];
  22.             dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
  23.             dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
  24.             dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
  25.             dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
  26.         }
  28.         return dp[size - 1][4];
  30.     }
  31. }

优化空间

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  4.         /**dp[0] 没有操作
  5.          * dp[1] 第一次买入
  6.          * dp[2] 第一次卖出
  7.          * dp[3] 第二次买入
  8.          * dp[4] 第二次卖出
  9.          */
  11.         int size = prices.length;
  12.         int [] dp = new int[5];
  14.         dp[0] = 0; 
  15.         dp[1] = -prices[0]; 
  16.         dp[2] = 0;
  17.         dp[3] = -prices[0];
  18.         dp[4] = 0;
  20.         for(int i = 1; i < size; i++ ) {
  21.             dp[0] = dp[0];
  22.             dp[1] = Math.max(dp[1],dp[0] - prices[i]);
  23.             dp[2] = Math.max(dp[2],dp[1] + prices[i]);
  24.             dp[3] = Math.max(dp[3],dp[2] - prices[i]);
  25.             dp[4] = Math.max(dp[4],dp[3] + prices[i]);
  26.         }
  28.         return dp[4];
  30.     }
  31. }