Best Time to Buy and Sell Stock I / II / III / IV / with cooldown / with Transaction Fee买卖股票6题

谁借莪１个温暖的怀抱￠ 2022-06-01 13:52 79阅读 0赞

## 121.Best Time to Buy and Sell Stock I ##

**题意：**用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。 如果只允许进行一次交易，也就是说只允许买一支股票并卖掉，求最大的收益。

**分析：**动态规划法。从前向后遍历数组，记录当前出现过的最低价格，作为买入价格，并计算以当天价格出售的收益，作为可能的最大收益，整个遍历过程中，出现过的最大收益就是所求。

**复杂度：**时间O(n)，空间O(1)。

class Solution \{  
public:  
int maxProfit(vector<int>& prices) \{  
int res = 0, cur\_min = INT\_MAX;  
for (int i = 0; i < prices.size(); i++) \{  
cur\_min = min(cur\_min, prices\[i\]);  
res = max(res, prices\[i\] - cur\_min);  
\}  
return res;  
\}  
\};

## 122.Best Time to Buy and Sell Stock II ##

**题目：**用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。交易次数不限，但一次只能交易一支股票，也就是说手上最多只能持有一支股票，求最大收益。

**复杂度：**时间O(n)，空间O(1)。

class Solution \{  
public:  
int maxProfit(vector<int>& prices) \{  
// version 1: 贪心法。从前向后遍历数组，只要当天的价格高于前一天的价格，就算入收益。  
/\*  
int res = 0;  
for (int i = 1; i < prices.size(); i++) \{  
res += prices\[i\] > prices\[i - 1\] ? prices\[i\] - prices\[i - 1\] : 0;  
\}  
return res;  
\*/  
// version 2: buy: buy state, sell: sell state 动态规划一天买入状态的最大收益有两种情况，之前就是买入状态或者今天刚买入，取最大值，卖出状态同理。  
if (prices.empty()) \{  
return 0;  
\}  
int buy = -prices\[0\], sell = 0;  
for (int i = 0; i < prices.size(); i++) \{  
buy = max(sell - prices\[i\], buy);  
sell = max(buy + prices\[i\], sell);  
\}  
return sell;

\}  
\};

上面这两种1次交易和无限次（n）次交易其实都是下面k次交易的特例

## 123.Best Time to Buy and Sell Stock III ##

**题意：**用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易两次，手上最多只能持有一支股票，求最大收益。

**分析1：**动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit\[i\]，和第i天之后进行一次交易的最大收益postProfit\[i\]，最后遍历一遍，max\{preProfit\[i\] + postProfit\[i\]\} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。

**复杂度：**时间O(n)，空间O(n)。

**// version 1**  
/\*  
if (prices.size() < 2) \{  
return 0;  
\}  
vector<int> left(prices.size(), 0);  
vector<int> right(prices.size(), 0);  
int min\_ = prices\[0\], max\_ = prices\[prices.size() - 1\], res = 0;  
for (int i = 1; i < prices.size(); i++) \{  
min\_ = min(min\_, prices\[i\]);  
left\[i\] = max(prices\[i\] - min\_, left\[i - 1\]);  
\}  
for (int i = prices.size() - 2; i >= 0; i--) \{  
max\_ = max(max\_, prices\[i\]);  
right \[i\] = max(max\_ - prices\[i\], right\[i + 1\]);  
\}  
for (int i = 1; i < prices.size(); i++) \{  
res = max(res, left\[i\] + right\[i\]);  
\}  
return res;

**分析2：由之前的两个状态变成4个状态**Buy1\[i\]表示前i天做第一笔交易买入状态最大收益；Sell1\[i\]表示前i天做第一笔交易卖出状态组大收益；Buy2\[i\] Sell2\[i\]同理；那么Sell2\[i\]=max\{Sell2\[i-1\],Buy2\[i-1\]+prices\[i\]\}；Buy2\[i\]=max\{Buy2\[i-1\],Sell\[i-1\]-prices\[i\]\}；Sell1\[i\]=max\{Sell\[i-1\],Buy1\[i-1\]+prices\[i\]\}； Buy1\[i\]=max\{Buy\[i-1\],-prices\[i\]\}。空间也可以优化成4个变量。

**复杂度：**时间O(n)，空间O(1)。

**//version 2**  
if (prices.size() < 2) \{  
return 0;  
\}  
int buy1 = INT\_MIN, buy2 = INT\_MIN, sell1 = 0, sell2 = 0;  
for (int i = 0; i < prices.size(); i++) \{  
buy1 = max(buy1, -prices\[i\]);  
sell1 = max(sell1, buy1 + prices\[i\]);  
buy2 = max(buy2, sell1 - prices\[i\]);  
sell2 = max(sell2, buy2 + prices\[i\]);  
\}  
return sell2;

**分析3：**下面的问题4的当k=2的特例。分析看下面k的情况

**复杂度：**时间O(n)，空间O(1)。

**代码们：**

class Solution \{  
public:  
/\*  
\* @param prices: Given an integer array  
\* @return: Maximum profit  
\*/  
int maxProfit(vector<int> &prices) \{  
// write your code here  
  
 **// version 3**  
if (prices.size() < 2) \{  
return 0;  
\}  
vector<int> global(3, 0);  
vector<int> local(3, 0);  
for (int i = 1; i < prices.size(); i++) \{  
int diff = prices\[i\] - prices\[i - 1\];  
for (int k = 2; k >= 1; k--) \{  
local\[k\] = max(global\[k - 1\], local\[k\]) + diff;  
global\[k\] = max(global\[k\], local\[k\]);  
\}  
\}  
return global\[2\];  
  
\}  
\};

## 188.Best Time to Buy and Sell Stock IV ##

**题意：**用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易k次，手上最多只能持有一支股票，求最大收益。

**分析1：**我们维护两种量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global\[i\]\[j\]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local\[i\]\[j\]）。下面我们来看递推式，全局的比较简单，

global\[i\]\[j\]=max(local\[i\]\[j\],global\[i-1\]\[j\])，

也就是去当前局部最好的，和过往全局最好的中大的那个（因为最后一次交易如果包含当前天一定在局部最好的里面，否则一定在过往全局最优的里面）。对于局部变量的维护，递推式是

local\[i\]\[j\]=max(global\[i-1\]\[j-1\]+max(diff,0),local\[i-1\]\[j\]+diff)，

也就是看两个量，第一个是全局到i-1天进行j-1次交易，然后加上今天的交易，如果今天是赚钱的话（也就是前面只要j-1次交易，最后一次交易取当前天），第二个量则是取local第i-1天j次交易，然后加上今天的差值（这里因为local\[i-1\]\[j\]比如包含第i-1天卖出的交易，所以现在变成第i天卖出，并不会增加交易次数，而且这里无论diff是不是大于0都一定要加上，因为否则就不满足local\[i\]\[j\]必须在最后一天卖出的条件了）。上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n\*k),但是注意当K大于天数的时候，这时候就变成了可以进行无穷多次交易了，此时还用dp就会超时，应该用股票类问题2中的贪心算法。还有一点，在dp空间优化成1维的时候，用一维数组来代替二维数组，可以极大的节省了空间，由于覆盖的顺序关系，我们需要j从2到1，这样可以取到正确的g\[j-1\]值，而非已经被覆盖过的值。

其实上述的递推公式关于local\[i\]\[j\]的可以稍稍化简一下，我们之前定义的local\[i\]\[j\]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，第 i 天卖第 j 支股票的话，一定是下面的一种：

1. 今天刚买的  
那么 Local(i, j) = Global(i-1, j-1)  
相当于啥都没干

2. 昨天之前卖掉的，昨天刚买的  
那么 Local(i, j) = Global(i-1, j-1) + diff  
等于Global(i-1, j-1) 中的交易，加上今天干的那一票

3. 更早之前买的  
那么 Local(i, j) = Local(i-1, j) + diff  
昨天别卖了，留到今天卖

但其实第一种情况是不需要考虑的，因为当天买当天卖不会增加利润，完全是重复操作，这种情况可以归纳在global\[i-1\]\[j-1\]中，所以我们就不需要max(0, diff)了，那么由于两项都加上了diff，所以我们可以把diff抽到max的外面，所以更新后的递推公式为：

local\[i\]\[j\] = max(global\[i - 1\]\[j - 1\], local\[i - 1\]\[j\]) + diff

global\[i\]\[j\] = max(local\[i\]\[j\], global\[i - 1\]\[j\])

给出代码：

int maxProfit(int K, vector<int> &prices) \{  
// write your code here  
if (prices.size() < 2 || K < 1) \{  
return 0;  
\}  
if (K >= prices.size()) return solveMaxProfit(prices);  
vector<int> local(K + 1, 0);  
vector<int> global(K + 1, 0);  
for (int i = 1; i < prices.size(); i++) \{  
int diff = prices\[i\] - prices\[i - 1\];  
for (int j = K; j >= 1; j--) \{  
local\[j\] = max(global\[j - 1\] + max(diff, 0), local\[j\] + diff);  
global\[j\] = max(global\[j\], local\[j\]);  
\}  
\}  
return global\[K\];  
\}  
int solveMaxProfit(vector<int> &prices) \{  
int res = 0;  
for (int i = 1; i < prices.size(); ++i) \{  
if (prices\[i\] - prices\[i - 1\] > 0) \{  
res += prices\[i\] - prices\[i - 1\];  
\}  
\}  
return res;  
\}

**复杂度：**时间O(n)，空间O(k)。

**分析2：**跟上面问题3的第二种思路的扩展，把2扩展成k即可

vector<int> buy(K + 1, INT\_MIN);  
vector<int> sell(K + 1, 0);  
for (int i = 0; i < prices.size(); i++) \{  
for (int j = 1; j < K + 1; j++) \{  
buy\[j\] = max(buy\[j\], sell\[j - 1\] - prices\[i\]);  
sell\[j\] = max(sell\[j\], buy\[j\] + prices\[i\]);  
\}  
\}  
return sell\[K\];

不过同样记得判断当K很大时的情况啊。

**复杂度：**时间O(n)，空间O(k)。

## 309.Best Time to Buy and Sell Stock with cooldown ##

而这道题与上面这些不同之处在于加入了一个冷冻期Cooldown之说，就是如果某天卖了股票，那么第二天不能买股票，有一天的冷冻期。此题需要维护三个一维数组buy, sell，和rest。其中：

buy\[i\]表示在第i天之前最后一个操作是买，此时的最大收益。

sell\[i\]表示在第i天之前最后一个操作是卖，此时的最大收益。

rest\[i\]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。

我们写出递推式为：

buy[i]  = max(rest[i-1] - price, buy[i-1]) 
    sell[i] = max(buy[i-1] + price, sell[i-1])
    rest[i] = max(sell[i-1], buy[i-1], rest[i-1])

上述递推式很好的表示了在买之前有冷冻期，买之前要卖掉之前的股票。一个小技巧是如何保证\[buy, rest, buy\]的情况不会出现，这是由于buy\[i\] <= rest\[i\]， 即rest\[i\] = max(sell\[i-1\], rest\[i-1\])，这保证了\[buy, rest, buy\]不会出现。

另外，由于冷冻期的存在，我们可以得出rest\[i\] = sell\[i-1\]，这样，我们可以将上面三个递推式精简到两个，其实也可以直接理解为就是只能卖了隔一天才能买，所以递推买的时候要用两天前的数据。

buy[i]  = max(sell[i-2] - price, buy[i-1]) 
    sell[i] = max(buy[i-1] + price, sell[i-1])

我们还可以做进一步优化，由于i只依赖于i-1和i-2，所以我们可以在O(1)的空间复杂度完成算法

代码：

int maxProfit(vector<int>& prices) \{  
if (prices.size() < 2) \{  
return 0;  
\}  
int buy = -prices\[0\], sell = 0, sell\_cache = 0;  
for (int i = 1; i < prices.size(); i++) \{  
buy = max(buy, sell\_cache - prices\[i\]);  
sell\_cache = sell;  
sell = max(sell, buy + prices\[i\]);  
\}  
return sell;

## 714.Best Time to Buy and Sell Stock with Transaction fee ##

给定一组某一stock在每一天的价格，买卖次数不限，每次买入必须在卖出之后，且每次卖出时都需要fee的手续费，求解最大的收益。

buy\[i\] 表示第i天的买收益的最大

sell\[i\] 表示第i天的卖收益的最大

接着填写初时状态

buy\[0\] = - prices\[0\] ( 我们买了第一件）

sell\[0\] = 0 （没法卖，没有收益）

接着是状态转移

buy\[i\] = max( sell\[i-1\] - prices\[i\], buy\[i-1\]);  
( 前一天卖了后今天买了， 前一天的最大）

sell\[i\] = max( buy\[i-1\] + prices\[i\] - fee , sell\[i-1\]);

总结：

几种转移方程的思路：