123. 买卖股票的最佳时机 III ——【Leetcode每日一题】

矫情吗；* 2024-03-25 21:26 36阅读 0赞

题目来源：[力扣。][Link 1]

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

给定一个数组，它的第 `i` 个元素是一支给定的股票在第 `i` 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 **两笔** 交易。

**注意：** 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

##### 示例 1: #####

> 输入：prices = \[3,3,5,0,0,3,1,4\]  
> 输出：6  
> 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3。  
> 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。

##### 示例 2： #####

> 输入：prices = \[1,2,3,4,5\]  
> 输出：4  
> 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
> 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
> 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

##### 示例 3： #####

> 输入：prices = \[7,6,4,3,1\]  
> 输出：0  
> 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

##### 示例 4： #####

> 输入：prices = \[1\]  
> 输出：0

##### 提示： #####

*   1 < = p r i c e s . l e n g t h < = 1 0 5 1 <= prices.length <= 10^5 1<=prices.length<=105
 *   0 < = p r i c e s \[ i \] < = 1 0 5 0 <= prices\[i\] <= 10^5 0<=prices\[i\]<=105

#### 思路：(动态规划) ####

1.  动态规划问题最重要的是先**确定一共有哪些状态**；
2.  然后分析每种状态的关系，从而确定 **状态转移方程**。

**第一步：确定所有的状态：**

本题的关键在于**至多买卖两次**，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

*  我们**随意看某一天**，这一天结束后：**可能**没有任何买卖，即没有任何操作；**可能**已经买了一次；**可能**已经买卖一次，即第一次卖出了；**可能**第二次买入了；**也可能**第二次卖出了；共有 5 种状态：
    
     *  1、没有任何操作
     *  2、第一次买入
     *  3、第一次卖出
     *  4、第二次买入
     *  5、第二次卖出

**第二步：分析每种状态的关系，确定状态转移方程：**

*  定义`dp[i]` 表示第`i` 的结束后的状态，一共五种可能，分被定义为：`dp[i][0]`、`dp[i][1]`、`dp[i][2]`、`dp[i][3]`、`dp[i][4]`。即：`dp[i][j]`表示第`i`天状态`j`所能获取的最大利润。
    
     *  `dp[i][0]` 第`i`天结束后，没有任何买卖，所以： d p \[ i \] \[ 0 \] = 0 dp\[i\]\[0\] = 0 dp\[i\]\[0\]=0
     *  `dp[i][1]` 第`i`天结束后，已经买入了一次股票，有两种情况：第`i`天前就已经买入，或者当天买入的，求最大利润，所以取最大值，即： d p \[ i \] \[ 1 \] = m a x ( d p \[ i − 1 \] \[ 1 \] , d p \[ i − 1 \] \[ 0 \] − p r i c e s \[ i \] ) dp\[i\]\[1\] = max(dp\[i - 1\]\[1\] , dp\[i - 1\]\[0\] - prices\[i\]) dp\[i\]\[1\]=max(dp\[i−1\]\[1\],dp\[i−1\]\[0\]−prices\[i\])
     *  `dp[i][2]` 第`i`天结束后，已经卖了一次股票，有两种情况：第`i`天前就已经卖出，或者当天卖出的，求最大利润，所以取最大值，即： d p \[ i \] \[ 2 \] = m a x ( d p \[ i − 1 \] \[ 2 \] , d p \[ i − 1 \] \[ 1 \] + p r i c e s \[ i \] ) dp\[i\]\[2\] = max(dp\[i - 1\]\[2\] , dp\[i - 1\]\[1\] + prices\[i\]) dp\[i\]\[2\]=max(dp\[i−1\]\[2\],dp\[i−1\]\[1\]\+prices\[i\])
     *  `dp[i][3]` 第`i`天结束后，已经买入二次股票，有两种情况：第`i`天前就已经买入，或者当天买入的，求最大利润，所以取最大值，即： d p \[ i \] \[ 3 \] = m a x ( d p \[ i − 1 \] \[ 3 \] , d p \[ i − 1 \] \[ 2 \] − p r i c e s \[ i \] ) dp\[i\]\[3\] = max(dp\[i - 1\]\[3\] , dp\[i - 1\]\[2\] - prices\[i\]) dp\[i\]\[3\]=max(dp\[i−1\]\[3\],dp\[i−1\]\[2\]−prices\[i\])
     *  `dp[i][4]` 第`i`天结束后，已经卖了两次股票，有两种情况：第`i`天前就已经卖出，或者当天卖出的，求最大利润，所以取最大值，即： d p \[ i \] \[ 4 \] = m a x ( d p \[ i − 1 \] \[ 4 \] , d p \[ i − 1 \] \[ 3 \] + p r i c e s \[ i \] ) dp\[i\]\[4\] = max(dp\[i - 1\]\[4\] , dp\[i - 1\]\[3\] + prices\[i\]) dp\[i\]\[4\]=max(dp\[i−1\]\[4\],dp\[i−1\]\[3\]\+prices\[i\])

最大利润肯定在卖出的状态，而两次卖出的状态利润最大，一定是在第二次卖出，即最大利润为：  
 d p \[ n − 1 \] \[ 4 \] dp\[n - 1\]\[4\] dp\[n−1\]\[4\]

**空间优化：**  
观察发现，`dp[i][j]` 只和 **前一天** 以及 **五种状态的上一个状态** 有关，

*  即可以只设五个变量对应五个状态即可，而第一种状态`dp[i][0]` 始终为 0 ，所以只需**四个变量**，动态变化：  
    分别为：`firstBuy` 、`firstSell`、`secondBuy`、`secondSell`

从而和上面对应为：  
`dp[i][1]` ：  
 f i r s t B u y = m a x ( f i r s t B u y ， − p r i c e s \[ i \] ) firstBuy = max(firstBuy，-prices\[i\]) firstBuy=max(firstBuy，−prices\[i\])  
`dp[i][2]` ：  
 f i r s t S e l l = m a x ( f i r s t S e l l , f i r s t B u y + p r i c e s \[ i \] ) firstSell=max(firstSell, firstBuy + prices\[i\]) firstSell=max(firstSell,firstBuy\+prices\[i\])  
`dp[i][3]` ：  
 s e c o n d B u y = m a x ( s e c o n d B u y ， f i r s t S e l l − p r i c e s \[ i \] ) secondBuy = max(secondBuy，firstSell - prices\[i\]) secondBuy=max(secondBuy，firstSell−prices\[i\])  
`dp[i][4]` ：  
 s e c o n d S e l l = m a x ( s e c o n d S e l l , s e c o n d B u y + p r i c e s \[ i \] ) secondSell = max(secondSell, secondBuy + prices\[i\]) secondSell=max(secondSell,secondBuy\+prices\[i\])

#### 代码：(Java) ####

public class MaxProfit3 {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int[] prices = {
        3,3,5,0,0,3,1,4};
    		System.out.println(maxProfit(prices));
    	}
    	public static int maxProfit(int[] prices) {
        
    		if(prices.length == 1) {
        
    			return 0;
    		}
    		int n = prices.length;
    		int [][] dp = new int [n][5];
    		
    		//dp[i][0]没有任何操作,一直为0
    		
    		//初始化
    		dp[0][1] = -prices[0];
    		// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
    		dp[0][3] = -prices[0];
    		
    		for(int i = 1; i < n; i++) {
        
    			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];
        }
    }

**空间优化：**

public class MaxProfit3 {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int[] prices = {
        3,3,5,0,0,3,1,4};
    		System.out.println(maxProfit(prices));
    	}
    	public static int maxProfit(int[] prices) {
        
    		if(prices.length == 1) {
        
    			return 0;
    		}
    		int n = prices.length;
    		//初始化
    		int firstBuy = -prices[0], firstSell = 0;
    		// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
    		int secondBuy = -prices[0], secondSell = 0;
    		
    		for(int i = 1; i < n; i++) {
        
    			firstBuy = Math.max(firstBuy, -prices[i]);
    			firstSell = Math.max(firstSell, firstBuy + prices[i]);
    			secondBuy = Math.max(secondBuy, firstSell - prices[i]);
    			secondSell = Math.max(secondSell, secondBuy + prices[i]);
    		}
    		return secondSell;
        }
    }

##### 运行结果： #####

![在这里插入图片描述][54c74f71208e4f3097632d38c63b5830.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，要遍历数组`prices`, n 为数组`prices`的长度。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)，优化后只需要常量级别的空间，优化前的空间复杂度为 O ( n ∗ 5 ) O(n \* 5) O(n∗5)，需要  n ∗ 5 n \* 5 n∗5 的空间。

**相同题目进阶：**

[188. 买卖股票的最佳时机 IV][188. _ IV]

##### 注：仅供学习参考！ #####

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
[54c74f71208e4f3097632d38c63b5830.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ea58df2c62d64a72a4fedfac6a9fcc24.png
[188. _ IV]: https://blog.csdn.net/weixin_43412762/article/details/129685795