### table of Contents

- 121. The best time to buy and sell stocks
- 122. The Best Time to Buy and Sell Stocks II
- 123. The best time to buy and sell stocks III
- 188. The Best Time to Buy and Sell Stock IV
- 309. The best time to buy and sell stocks includes a freezing period
- 714. The best time to buy and sell stocks includes handling fees

# 121. The best time to buy and sell stocks

## greedy

Take the leftmost minimum value, take the rightmost maximum value, and the difference is the maximum profit

```
class Solution {
public :
int maxProfit (vector< int >& prices) {
int n = prices. size ();
int minprice = prices[ 0 ];
int maxpro = 0 ;
for ( int i = 1 ; i <n; i++ )
{
minprice = min (prices[i],minprice);
maxpro = max (prices[i]-minprice,maxpro);
}
return maxpro;
}
};
Copy code
```

## dp ideas

step1:

step2:

If you hold stocks on day i

case1: The i-1th holds the stock and keep the status quo,

case2: If you buy stocks on the i day, the cash you get is the cash you get after buying today's stocks. which is

If no stocks are held on day i

case1: The i-1th does not hold stocks, keep the status quo,

case2: hold the stock on the i-1, sell it on the i day,

step3: The

initial state is

final result

```
class Solution {
public :
int maxProfit (vector< int >& prices) {
int n = prices. size ();
vector<vector< int >> dp (n,vector< int >( 2 , 0 ));
dp[ 0 ][ 0 ] = -prices[ 0 ];
dp[ 0 ][ 1 ] = 0 ;
for ( int i = 1 ; i <n; i++)
{
//holds
DP [I] [ 0 ] = max (DP [I -1 ] [ 0 ], - Prices [I]);
//not holding
DP [I] [ . 1 ] = max (DP [I - 1 ][ 1 ],dp[i -1 ][ 0 ]+prices[i]);
}
return dp[n -1 ][ 1 ];
}
};
Copy code
```

## Scrolling array optimization

Since only two states of dp[i] and dp[i-1] are used, only a 2 * 2 array is needed.

```
class Solution {
public :
int maxProfit (vector< int >& prices) {
int n = prices. size ();
vector<vector< int >> dp ( 2 ,vector< int >( 2 , 0 ));
dp[ 0 ][ 0 ] = -prices[ 0 ];
dp[ 0 ][ 1 ] = 0 ;
for ( int i = 1 ; i <n; i++)
{
//Hold
dp[i% 2 ][ 0 ] = max (dp[(i -1 )% 2 ][ 0 ],-prices[i]);
//Do not hold
dp[i% 2 ][ 1 ] = max (dp[(i -1 )% 2 ][ 1 ],dp[(i -1 )% 2 ][ 0 ]+prices[i]);
}
return dp[(n -1 )% 2 ][ 1 ];
}
};
Copy code
```

# 122. The Best Time to Buy and Sell Stocks II

the ith day If you hold stocks on the ith day, then

case1: hold the stock on day i-1 and maintain the status quo, then

case2: The stock is bought on the i day, and the cash is the cash that did not hold the stock yesterday minus the stock price today

If no stock is held on day i, then

case1: do not hold stocks on day i-1, keep the status quo,

case2: hold stock on day i-1, sell on day i,

```
class Solution {
public :
int maxProfit (vector< int >& prices) {
int n = prices. size ();
vector<vector< int >> dp ( 2 ,vector< int >( 2 , 0 ));
dp[ 0 ][ 0 ] = -prices[ 0 ];
dp[ 0 ][ 1 ] = 0 ;
for ( int i = 1 ; i <n; i++)
{
dp[i% 2 ][ 0 ] = max (dp[(i -1 )% 2 ][ 0 ],dp[(i -1 )% 2 ][ 1 ]-prices[i]);
dp[i% 2 ][ 1 ] = max (dp[(i -1 )% 2 ][ 1 ],dp[(i -1 )% 2 ][ 0 ]+prices[i]);
}
return dp[(n -1 )% 2 ][ 1 ];
}
};
Copy code
```

# 123. The best time to buy and sell stocks III

It can be bought and sold twice at most, either once or twice, or not.

Each day consists of five states:

0, no operation,

1, first purchase

2, first sale

3, second purchase

4, second sale

2, it is determined recursion formulas

Examples

achieve

case1: buy stocks on the i day, then

case2: There is no operation on the i day, then

same reason

case1: the stock is sold on the i day, then

case2: There is no operation on the i day, and the status of the stock sold the day before is used, that is:

and so

The same

case1: buy stocks on the i day,

case2: There is no operation on the i day, and the state of buying the stock the day before is used, namely:

The same

case1: sell the stock on the i day,

case2: There is no operation on the i day, and the status of the stock sold the day before is used, that is:

So how to initialize it?

If there is no operation on day 0,

If you do the first buy operation on day 0,

Do the first sell operation on day 0, and this initial value is 0.

Buy the second time on day 0, no matter how many times, there is no money on hand, you can only reduce

Sell for the second time on day 0,

```
class Solution {
public :
int maxProfit (vector< int >& prices) {
int n = prices. size ();
vector<vector< int >> dp (n,vector< int >( 5 , 0 ));
//dp[0][0] = 0;
dp[ 0 ][ 1 ] = -prices[ 0 ];
//dp[0][2] = 0;
dp[ 0 ][ 3 ] = -prices[ 0 ];
//dp[0][4] = 0;
for ( int i = 1 ; i <n; i++)
{
dp[i][ 0 ] = dp[i -1 ][ 0 ];
dp[i][ 1 ] = max (dp[i -1 ][ 1 ],dp[i -1 ][ 0 ]-prices[i]);
dp[i][ 2 ] = max (dp[i -1 ][ 2 ],dp[i -1 ][ 1 ]+prices[i]);
dp[i][ 3 ] = max (dp[i -1 ][ 3 ],dp[i -1 ][ 2 ]-prices[i]);
dp[i][ 4 ] = max (dp[i -1 ][ 4 ],dp[i -1 ][ 3 ]+prices[i]);
}
return dp[n -1 ][ 4 ];
}
};
Copy code
```

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

step1:

This question is an advanced version of the previous question, which defines a two-dimensional dp array.

Use a two-dimensional array

The status of j is expressed as:

0 no operation, 1 first purchase, 2 first sale, ...

Except for 0, even numbers are selling, and odd numbers are buying. Because there are at most k transactions, the range of j is defined as 2*k+1.

```
Vector <Vector < int >> DP (Prices. size (), Vector < int > ( 2 * K + . 1 , 0 ));
duplicated code
```

step2:

```
for ( int j = 0 ; j < 2 * k- 1 ; j+= 2 )
{
//Odd, indicating to buy
dp[i][j+ 1 ] = max (dp[i -1 ][j+ 1 ],dp[i -1 ][j]-prices[i]);
//even, indicating Sell
dp[i][j+ 2 ] = max (dp[i -1 ][j+ 2 ],dp[i -1 ][j+ 1 ] + prices[i]);
}
Copy code
```

step3:

Initialization, as long as it is a buying operation, the cash will be reduced accordingly, and the initial value of the selling operation will be 0

```
for ( int j = 1 ; j < 2 *k; j += 2 )
{
dp[ 0 ][j] = -prices[ 0 ];
}
Copy code
```

AC code:

```
class Solution {
public :
int maxProfit ( int k, vector< int >& prices) {
int n = prices. size ();
if (n == 0 || k == 0 ) return 0 ;
vector<vector< int >> dp (n,vector< int >(k* 2 + 1 , 0 ));
for ( int i = 1 ; i <= 2 *k; i += 2 )
dp[ 0 ][i] = -prices[ 0 ];
for ( int i = 1 ; i <n; i++)
{
for ( int j = 0 ; j <= 2 * k- 2 ; 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];
}
};
Copy code
```

# 309. The best time to buy and sell stocks includes a freezing period

State 1: The state of buying stocks (maybe it was bought today, or it may have been bought before and then no operation)

. There are two

states of selling stocks: State 2: The stock was sold two days ago, degree after a freezing period and has not been operating, selling stock today remains state

state three: today sold stock

status four: today is the freezing of the state, but the frozen state of unsustainable, only one day

recurrence formula is as follows:

arrival buy Into the stock status (status 1) namely

case1: It was in this state the day before, and this state is used today

Case2: Buy today, there are two situations (state 4) the

previous day was the freezing period, and the previous day was the state of keeping the stock sold (state 2), both of which are possible to buy today

, namely:

Reaching the state of keeping sold (state two) namely:

case1: the previous day is the second state, and continue to use this state

case2: the previous day is the freezing period (state four)

It reaches the state of selling stocks today (state three), there is only one state, the previous day was state one, and then selling today

The freezing period state (state 4) has been reached, there is only one state, and the stock has just been sold the day before

In summary, the recurrence code is:

```
dp[i][ 0 ] = max (dp[i -1 ][ 0 ], max (dp[i -1 ][ 3 ],dp[i -1 ][ 1 ])-prices[i]);
dp[i][ 1 ] = max (dp[i -1 ][ 1 ],dp[i -1 ][ 3 ]);
dp[i][ 2 ] = dp[i -1 ][ 0 ] + prices[i];
dp[i][ 3 ] = dp[i -1 ][ 2 ];
Copy code
```

Regarding the initialization of the dp array:

state one, holding stocks, then

Status two, keep selling status,

State three, just sold the stock, there will be no income either

State four, freezing period,

The final result is to select the maximum value from state two to state four.

```
class Solution {
public :
int maxProfit (vector< int >& prices) {
int n = prices. size ();
vector<vector< int >> dp (n,vector< int >( 4 , 0 ));
dp[ 0 ][ 0 ] = -prices[ 0 ];
for ( int i = 1 ; i <n; i++)
{
dp[i][ 0 ] = max (dp[i -1 ][ 0 ], max (dp[i -1 ][ 1 ],dp[i -1 ][ 3 ])-prices[i]);
dp[i][ 1 ] = max (dp[i -1 ][ 1 ],dp[i -1 ][ 3 ]);
dp[i][ 2 ] = dp[i -1 ][ 0 ] + prices[i];
dp[i][ 3 ] = dp[i -1 ][ 2 ];
}
return max (dp[n -1 ][ 1 ], max (dp[n -1 ][ 2 ],dp[n -1 ][ 3 ]));
}
};
Copy code
```

# 714. The best time to buy and sell stocks includes handling fees

Compared with 122. The best time to buy and sell stocks II, subtract more operating expenses.

```
class Solution {
public :
int maxProfit (vector< int >& prices, int fee) {
int n = prices. size ();
vector<vector< int >> dp ( 2 ,vector< int >( 2 , 0 ));
dp[ 0 ][ 0 ] = -prices[ 0 ];
dp[ 0 ][ 1 ] = 0 ;
for ( int i = 1 ; i <n; i++)
{
//Hold
dp[i% 2 ][ 0 ] = max (dp[(i -1 )% 2 ][ 0 ],dp[(i -1 )% 2 ][ 1 ]-prices[i]) ;
//Do not hold
dp[i% 2 ][ 1 ] = max (dp[(i -1 )% 2 ][ 1 ],dp[(i -1 )% 2 ][ 0 ]+prices[i ]-fee);
}
return dp[(n -1 )% 2 ][ 1 ];
}
};
Copy code
```