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

文章目录 Tag题目来源题目解读解题思路方法一：动态规划 写在最后

Tag

【动态规划】【数组】【2023-10-04】

---

题目来源

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

---

题目解读

本题与 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II、123. 买卖股票的最佳时机 III 题意目的一致，都是为了获得买卖股票的最大利润。本题不同的是，最多可以买卖股票 k 次。

---

解题思路 方法一：动态规划

首先来看一下 k，虽然给定了最多可以买卖 k 次，但是 n 天做多可以买卖 ⌊ n 2 ⌋ \lfloor \frac{n}{2} \rfloor ⌊2n​⌋ 次，因此需要更新 k = m i n ( k , ⌊ n 2 ⌋ ) k = min(k, \lfloor \frac{n}{2} \rfloor) k=min(k,⌊2n​⌋)。

状态

122. 买卖股票的最佳时机 II 中最多允许进行两次股票的买卖，我们主要有四种状态，分别是第一次买、第一次卖，第二次买和第二次卖。在本题中最多有 k 次股票的买卖就有 k * 2 次的状态，我们可以使用数组来维护。 b u y [ i ] buy[i] buy[i] 表示第 i 次买股票， s e l l [ i ] sell[i] sell[i] 表示第 i 次卖股票。

状态转移

我们的第 i 次买股票手中剩余的最大钱数（也就是最大利润） b u y [ i ] = m a x ( b u y [ i ] , s e l l [ i − 1 ] − p r i c e s [ i ] ) buy[i] = max(buy[i], sell[i-1] - prices[i]) buy[i]=max(buy[i],sell[i−1]−prices[i])。

同理， s e l l [ i ] = m a x ( s e l l [ i ] , b u y [ i − 1 ] + p r i c e s [ i ] ) sell[i] = max(sell[i], buy[i-1] + prices[i]) sell[i]=max(sell[i],buy[i−1]+prices[i])。

base case

第 i 次买，我们都初始为 int 类型的最小值，因为买股票手中的钱可能出现负数。为了防止溢出，选择初始化为 INT_MIN / 2。

第 i 次卖股票，我们初始化为 0，因为不会再有比 0 小的卖股票收益了。

最后返回

最后返回 sell.back() 即 sell 数组的最后一个值，即使最大值是 sell 数组中的某一个值，也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，最终最大值也是转移到 sell 数组的最后一个值（具体可参考 解题思路中的 最后返回 部分）。

实现代码

class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); k = min(k, n / 2); vector<int> buy(k+1, INT_MIN / 2); // 防止 sell[i-1] - p 溢出 vector<int> sell(k+1, 0); for (int p : prices) { for (int i = 1; i <= k; ++i) { buy[i] = max(buy[i], sell[i-1] - p); sell[i] = max(sell[i], buy[i] + p); } } return sell.back(); } };

复杂度分析

时间复杂度： O ( n   m i n ( n , k ) ) O(n \ min(n, k)) O(n min(n,k))， n n n 是数组 prices 的大小。

空间复杂度： O ( m i n ( n , k ) ) O(min(n, k)) O(min(n,k))，使用的额外空间为数组 buy、sell 占用的空间。

---

写在最后

买卖股票系列题目

题目解答121. 买卖股票的最佳时机【面试经典150】买卖股票的最佳时机122. 买卖股票的最佳时机 II【面试经典150】买卖股票的最佳时机 II123. 买卖股票的最佳时机 III【每日一题】买卖股票的最佳时机 III309. 买卖股票的最佳时机含冷冻期【每日一题】买卖股票的最佳时机含冷冻期714. 买卖股票的最佳时机含手续费【每日一题】买卖股票的最佳时机含手续费

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。