买卖股票的最佳时机 - 合集
*************
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
- have stocks
- have not stocks
for having a stock
- 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]); // 如果今天卖出股票，利润是之前持有股票的最大利润加上今天的价格