## [Leetcode]188. Best Time to Buy and Sell Stock IV (C++)

### 题目描述

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

### 例子

#### 例子 1

Input: [2,4,1], k = 2 Output: 2 Explanation:Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

#### 例子 2

Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

### 解题思路

#### 方法一

``````#include <vector>
#include<bits/stdc++.h>

class Solution {
public:
int maxProfit(int k, std::vector<int>& prices) {
if (k == 0 || prices.size() <= 1) return 0;
if (k > prices.size()) k = prices.size() / 2;
std::vector<int> kth_sell(k, 0);

for (int currentPrice: prices) {
for (int i = k - 1; i > 0; i--) {
kth_sell[i] = std::max(kth_sell[i], currentPrice + kth_buy[i]);
}
kth_sell[0] = std::max(kth_sell[0], currentPrice + kth_buy[0]);
}

return kth_sell.back() < 0? 0 : kth_sell.back();
}
};
``````
• 时间复杂度: O(kn)
• 空间复杂度: O(k)

#### 方法二

Built with Hugo
Theme Stack designed by Jimmy