买卖股票的最佳时机 - 合集

*************

C++

买卖股票问题合集

*************

Since I have finished some stocks problems. I wanna make a list of the stocks to figure out the similarities.

Here is the storks topucs list, from easy to hard:

121. 买卖股票的最佳时机 - 力扣（LeetCode）

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）\

here I will introduce a very professional upper about stocks - bilibili ID - 小Lin说

In my opinion, topic 309 is the most harder one and I fail to solve it.

Start from the EZ one:121. 买卖股票的最佳时机 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

With no hesitation, only two states in a day, to be or not to be, in other word, Buy or sale.

Make int Buy is the profit in the day i while buy one;

Make int Sale is the profit in the day i while sale one;

If I have stocks today, two situations,  1 is that you bought it days before today; 2 is that you buy it today. So today's max profit is max(Buy, - prices[i]);

If I donnot have stocks today, two situations, 1 is that you sale it the day before today and today you donnot plan to buy too, so today's profit is int Sale; 2 is you sale iyt today, and today's profit is int Buy + prices[i];

the most important concept is here:

Buy = max(Buy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
Sale = max(Sale, Buy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格

 The whole code is as follow.

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.empty()) return 0; // 如果价格数组为空，返回0int Buy = -prices[0]; // 最初买入股票，利润为负数，因为还没有卖出int Sale = 0; // 最初不卖出股票，利润为0for (int i = 1; i < prices.size(); i++) {Buy = max(Buy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格Sale = max(Sale, Buy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格}return Sale; // 返回不持有股票的最大利润}
};

Go on. If you can trade twice during the whole period.

123. 买卖股票的最佳时机 III - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

 That is easy to write, just add another group of trading:

 If trading once during the whole period, the equation is as follow.

firstBuy = max(firstBuy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
firstSale = max(firstSale, firstBuy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格

now we have the second trading. As is known, second always comes after first:

firstBuy = max(firstBuy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
firstSale = max(firstSale, firstBuy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格// 加上第二次交易
secondBuy = max(secondBuy, firstSale - prices[i]);
secondSale = max(secondSale, prices[i] + secondBuy);

And the other code remains:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size(); // get the lengthint firstBuy = - prices[0];int firstSale = 0;int secondBuy = - prices[0];int secondSale = 0;// do sth. herefor (int i = 1; i < n; i++){firstBuy = max(firstBuy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格firstSale = max(firstSale, firstBuy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格// 加上第二次交易secondBuy = max(secondBuy, firstSale - prices[i]);secondSale = max(secondSale, prices[i] + secondBuy);}return secondSale;}
};

What if trading times is k?

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

the most important algorithm remains same:

Buy = max(Buy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
Sale = max(Sale, Buy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格

loops buy-sale group:

for (int i = 0; i < n; i++) {for (int j = 1; j <= k; j++) {// 更新买入状态，即在第i天买入第j次的最大利润buy[j] = max(buy[j], sell[j - 1] - prices[i]);// 更新卖出状态，即在第i天卖出第j次的最大利润sell[j] = max(sell[j], buy[j] + prices[i]);}}

the rest of the code remains.

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0);for (int i = 0; i < n; i++) {for (int j = 1; j <= k; j++) {// 更新买入状态，即在第i天买入第j次的最大利润buy[j] = max(buy[j], sell[j - 1] - prices[i]);// 更新卖出状态，即在第i天卖出第j次的最大利润sell[j] = max(sell[j], buy[j] + prices[i]);}}// 最后返回卖出状态的最大值，即进行k次交易的最大利润return sell[k];}};

What if the trading times are free?

122. 买卖股票的最佳时机 II - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

That comes easy. Buy in every low price and salt out when price is highher:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n <= 1) return 0;  // 如果数组为空或只有一个元素，直接返回0int profit = 0;for (int i = 0; i < n - 1; i++) {if (prices[i + 1] > prices[i]) {profit += prices[i + 1] - prices[i];}}return profit;}
};

What if you have to pay trading fee every time?

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

It looks like  122. 买卖股票的最佳时机 II - 力扣（LeetCode）, however make   profit += prices[i + 1] - prices[i] - fee; doesnot work.

 Think different, there is a treading time k, makes the max profit. So it is more like 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

I do remember the mostimportant algorithm

Buy = max(Buy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
Sale = max(Sale, Buy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();if (n <= 1) return 0;int Sale = 0; // 不持有股票的最大利润int Buy = -prices[0]; // 持有股票的最大利润for (int i = 1; i < n; i++) {int current_Sale = max(Sale, Buy + prices[i] - fee);int current_Buy = max(Buy, Sale - prices[i]);Sale = current_Sale;Buy = current_Buy;}return Sale;}
};

And the one I hate comes:309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

 Of course, like the last one, the most important algorithm is as follow.

Buy = max(Buy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
Sale = max(Sale, Buy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格

For every special day , there is 2 states

1. have stocks
2. have not stocks

for having a stock

1. have stocks 

•  buy today
• freeze day before today

for not having a stock

• sale today
• sale day before today and buy  no stocks today

But if I sale the stocks today, I cannot buy one tomorrow. So for not having stocks have two situations:

• sold: the profit of you donnot have a stock but in a freeze period which you cannot buy one
• rest: the profit of you donnot have a stock and not in a freeze period which you can buy one

so the code is easy

buy = max(buy, rest - prices[i]), the profit of you bought before or you buy todaysold = buy + price[i]rest = max(rest, sold)

and loop i

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.empty()) return 0;int n = prices.size();// 初始状态int buy = -prices[0];int sold = 0;int rest = 0;for (int i = 1; i < n; ++i) {int new_buy = max(buy, rest - prices[i]);int new_sold = buy + prices[i];int new_rest = max(rest, sold);buy = new_buy;sold = new_sold;rest = new_rest;}return max(sold, rest);}
};

the most important is as follow:
 

Buy = max(Buy, - prices[i]); // 如果今天买入股票，利润是之前不持有股票的最大利润减去今天的价格
Sale = max(Sale, Buy + prices[i]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格