# LeetCode best time to buy and sell stocks series summary

### LeetCode best time to buy and sell stocks series summary

This kind of dynamic programming is optimized from two-dimensional dynamic gauge to one-dimensional dynamic gauge. Greed can also be used in some problems.

#### catalog:

121 the best time to buy and sell stocks 1
122 the best time to buy and sell stocks 2
123the best time to buy and sell stocks 3
188 the best time to buy and sell stocks 4
309 the best time to buy and sell stocks + freezing period
714 best time to buy and sell stocks + handling fee (selling time handling fee based on 2)

#### 121 the best time to buy and sell stocks (once)

Given an array of prices, its ith element prices[i] represents the price of a given stock on day I.
You can only choose to buy this stock one day and sell it on a different day in the future. Design a
Algorithm to calculate the maximum profit you can make.
Return the maximum profit you can make from this transaction. If you can't make any profit, return 0.

Input: [7,1,5,3,6,4]
Output: 5 explanation: buy on day 2 (stock price = 1) and on day 5 (stock price=
6) When selling, the maximum profit = 6-1 = 5.
Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price; At the same time, you can't sell stocks before buying.

```Two dimensional dynamic gauge
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 1)return 0;
vector<vector<int>>dp(n, vector<int>(2));
dp[0][0] = 0;                 // Not held = sold + not bought
dp[0][1] = -prices[0];        // Have bought but not sold
for(int i = 1; i < n; ++i)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//Not held on day i = max (not held on day i - 1, held on day i - 1 + sold today)
dp[i][1] = max(dp[i - 1][1],  -prices[i]);
//Holding on day i = max (holding on day i - 1, buying today, only once)
}
return dp[n - 1][0];
}
```
```One dimensional kinematic gauge O(N)/O(1)
The status of each day is only related to the status of the previous day dp[i - 1][1],dp[i - 1][0]There are two variables,
Calculated dp[i][1],dp[i][0]Save back the corresponding variable
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 1)return 0;
int sell = 0;                // Not held = sold + not bought
int buy = -prices[0];        // Have bought but not sold
for(int i = 0; i < n; ++i)
{
int newsell = max(sell, buy + prices[i]);
sell = newsell;
}
return sell;
}
```
```Greed:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n == 1)return 0;
int maxn = 0;
int start = prices[0];
for(int i = 1; i < n; ++i)
{
if(prices[i] < start) start = prices[i];
//If the next price is less than the assumed purchase price, update start
else maxn = max(maxn, prices[i] - start);
//Update maximum profit
}
return maxn;
}
```

#### 122 the best time to buy and sell stocks 2 (buy and sell many times)

Give an array prices, where prices[i] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can complete as many transactions as possible (buying and selling a stock multiple times).
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

```Two dimensional dynamic gauge
Define status dp[i][1] Represents the second i There is no maximum profit of stocks after trading for days,
dp[i][0] Represents the second i The maximum profit of holding a stock after trading for days( i From 0).
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>>dp(n, vector<int>(2));
dp[0][0] = - prices[0];  //hold
dp[0][1] = 0;            //Not held
for(int i = 1; i < n; ++i)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//Holding on day i = max (holding on day i - 1, not holding on day i - 1, buying today) and 1 are different
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[n - 1][1];
}
};
```
```One dimensional kinematic gauge
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp0 = -prices[0];
int dp1 = 0;
for(int i = 1; i < n; ++i)
{
int newdp0 = max(dp0, dp1 - prices[i]);
int newdp1 = max(dp1, dp0 + prices[i]);
dp0 = newdp0;
dp1 = newdp1;
}
return dp1;
}
```
```Greedy, collect all uphill, and is the biggest
int maxProfit(vector<int>& prices) {
int n = prices.size();
int maxn = 0;
for(int i = 1; i < n; ++i)
{
maxn += max(0, prices[i] - prices[i - 1]);
}
return maxn;
}
```

#### 123 best time to buy and sell stocks (2 times)

Given an array, its ith element is the price of a given stock on day i.
Design an algorithm to calculate the maximum profit you can make. You can complete up to two transactions.
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

```Two dimensional dynamic gauge
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n <= 1)return 0;
vector<vector<int>>dp(n, vector<int>(5));
dp[0][0] = 0;                  //No operation
dp[0][1] = -prices[0];         //First purchase
dp[0][2] = 0;                  //First sale
dp[0][3] = -prices[0];         //Second purchase
dp[0][4] = 0;                  //Second sale
for(int i = 1; i < n; ++i)
{
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//First sale = max (sold the day before, bought the day before, sold today)
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//Second buying = max (second buying the day before, first selling the day before + buying today)
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
//Second sale = max (second purchase the day before. Second purchase the day before + sell today)
}
return dp[n - 1][4];
}
```
``` One dimensional dynamic gauge; The status of each day is only related to the status of the previous day
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n <= 1)return 0;
int sell1 = 0;
int sell2 = 0;
for(int i = 1; i < n; ++i)
{
sell1 = max(sell1, buy1 + prices[i]);
sell2 = max(sell2, buy2 + prices[i]);
}
return sell2;
}
```

#### 188 best time to buy and sell stocks (k times)

Given an integer array prices, its ith element prices[i] is the price of a given stock on day I.
Design an algorithm to calculate the maximum profit you can make. You can complete up to k transactions.
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

```Two dimensional dynamic gauge
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if(k == 0 || n == 0)return 0;
vector<vector<int>>dp(n, vector<int>(2*k + 1, 0));
for(int i = 1; i < 2*k; i += 2) dp[0][i] = -prices[0]; //Odd buy
for(int i = 1; i < n; i++)
{
for(int j = 0; j < 2*k - 1; j += 2)
{
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] -prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[n - 1][2*k];
}
```

#### 309 the best time to buy and sell stocks + freezing period

Given an array of integers, the ith element represents the stock price on day i.
Design an algorithm to calculate the maximum profit. You can complete as many transactions as possible (buying and selling a stock multiple times) under the following constraints:
You cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
After selling stocks, you can't buy stocks the next day (i.e. the freezing period is 1 day).

```Two dimensional dynamic gauge
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>>dp(n, vector<int>(3));
dp[0][0] = -prices[0];   //hold
dp[0][1] = 0;            //Not held, frozen
dp[0][2] = 0;            //Not held, not frozen
for(int i = 1; i < n; ++i)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
//Holding on day i = max (i - holding on day 1, i - not holding on day 1, not buying today)
dp[i][1] = dp[i - 1][0] + prices[i];
//Day i not held in frozen = i - 1 just sold
dp[i][2] = max(dp[i - 1][2],dp[i - 1][1]);
//Day i not held not frozen = max (i - day 1 not held not frozen, i - day 1 frozen)
}
return max(dp[n - 1][1], dp[n - 1][2]);
}
```

Added by interactive on Tue, 21 Dec 2021 18:41:28 +0200