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

旧城等待， 2024-03-25 22:17 74阅读 0赞

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

### 188. 买卖股票的最佳时机 IV ###

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

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

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

##### 示例 1： #####

> 输入：k = 2, prices = \[2,4,1\]  
> 输出：2  
> 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

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

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

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

*  0 <= k <= 100
 *  0 <= prices.length <= 1000
 *  0 <= prices\[i\] <= 1000

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

最多可以完成 `k` 笔交易, 是最多完成 `2` 次的升级版；  
具体解法和思路，请查看：  
[123. 买卖股票的最佳时机 III][123. _ III]

#### 代码：(Java、C++) ####

**Java**

public class MaxProfit4 {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int k = 2;
    		int[] prices = {
        2,4,1};
    		System.out.println(maxProfit(k, prices));
    	}
    	public static int maxProfit(int k, int[] prices) {
        
    		if(prices.length <= 1) {
        
    			return 0;
    		}
    		
    		int[] buy = new int[k + 1]; //共买卖k次
    		int[] sell = new int[k + 1]; 
    		
    		for(int i = 1; i < k + 1; i++) {
        //赋初值
    			buy[i] = - prices[0];
    		}
    		for(int i = 1; i < prices.length; i++) {
        
    			for(int j = 1; j <= k; j++) {
        
    				buy[j] = Math.max(buy[j], sell[j - 1] - prices[i]);//买
    				sell[j] = Math.max(sell[j], buy[j] + prices[i]);//卖
    			}
    		}
    		
    		return sell[k];
        }
    }

**C++**

#include<iostream>
    using namespace std;
    #include<vector>
    
    int maxProfit(int k, vector<int>& prices) {
        
    	if (prices.size() <= 1) {
        
    		return 0;
    	}
    	vector<int> buy(k + 1);
    	vector<int> sell(k + 1);
    
    	for (int i = 1; i <= k; i++) {
        
    		buy[i] = - prices[0];//初始化
    	}
    	for (int i = 1; i < prices.size(); i++) {
        
    		for (int j = 1; j <= k; j++) {
        
    			buy[j] = max(buy[j], sell[j - 1] - prices[i]); //买
    			sell[j] = max(sell[j], buy[j] + prices[i]); //卖
    		}
    	}
    	return sell[k];
    }
    int main()
    {
        
    	vector<int> prices = {
         2,4,1};
    	int k = 2;
    	cout << maxProfit(k, prices) << endl;
    	
    	return 0;
    }

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

![在这里插入图片描述][2bc78fde83614dcc980af0b3ee410a4e.png]  
**力扣提交：**  
![在这里插入图片描述][0e6a1f2e44fc45cc9a382f641a555365.png]

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

*  **时间复杂度**： O ( n ∗ k ) O(n\*k) O(n∗k)，`n`为数组`prices`的长度，`k`为最多完成的交易数。
 *  **空间复杂度**： O ( 2 ∗ k ) O(2\*k) O(2∗k)，`k`为最多完成的交易数。

##### 注：仅供学习参考， 如有不足，欢迎指正！ #####

[Link 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
[123. _ III]: https://blog.csdn.net/weixin_43412762/article/details/129664945
[2bc78fde83614dcc980af0b3ee410a4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/95d9ea1086a14289b7cdd05dc229da55.png
[0e6a1f2e44fc45cc9a382f641a555365.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/634f6d0331da4568ba2eb48747c7b5ab.png