author ：Grey
Original address ： A series of questions about the best time to buy and sell stocks
LeetCode 121. The best time to buy and sell stocks
Main idea ： Because only one share can be traded , So we can enumerate Must be i Position as a selling opportunity , What is the maximum benefit . If we get every i Maximum benefit of location , Then the maximum return must be the maximum value of the maximum return of all positions .
Use two variables ：
min Variable ： Indicates what is the minimum value before the traversed position .
max Variable ： Indicates that the current collection must be in i What is the maximum profit from selling location .
Traverse the array once , After traversing to i In position ,min and max The update logic of is as follows ：
min = Math.min(arr[i], min); // Every time I traverse arr[i] And the big picture min Compare , See if you can refresh min Value
max = Math.max(arr[i] - min, max); // arr[i] - min Must be expressed in i What is the biggest gain when selling a position , And the overall situation max value pk The maximum value of is given to max
After traversing the array , return max The value of is the final answer . For the full code, see ：
public class LeetCode_0121_BestTimeToBuyAndSellStock {
public int maxProfit(int[] arr) {
int max = 0;
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
min = Math.min(arr[i], min);
max = Math.max(arr[i] - min, max);
}
return max;
}
}
LeetCode 122. The best time to buy and sell stocks II
Main idea ： Because you can make any number of transactions , But you can only hold at most one share at any time , So we can put all of the stock curve Rising section All captured , Cumulative gain is the maximum gain . Traversal array , The traversed position subtracts the value of the previous position , If it's a positive number , Just collect , If it's a negative number , Just set this income as 0（ It's tantamount to not making this transaction ）, Traverse the array like this , You won't miss all the benefits .
Set a variable max, For the initial 0, Used to collect the maximum return value , Came to i Location ,max The update logic is as follows ：
max += Math.max((prices[i] - prices[i - 1]), 0);
The complete code is as follows ：
public int maxProfit(int[] prices) {
int max = 0;
for (int i = 1; i < prices.length; i++) {
// Catch all the ascents
max += Math.max((prices[i] - prices[i - 1]), 0);
}
return max;
}
A simple conclusion can be drawn from this question ： If the number of array elements is N, At most N/2 One transaction can capture the value of all rising segments （ In extreme cases , Buy... At this moment , Sell... At the next moment , Keep such a deal until the end , The number of transactions executed is N/2）.
LeetCode 188. The best time to buy and sell stocks IV
Main idea ：
- If
kThe value of is greater than or equal to half the length of the array , It's like an infinite number of transactions , In this case , You can directly use the solution of problem 2 to do . - If
kThe value of is less than half the length of the array , It needs to be considered separately .
In the 2 Under different circumstances , We define
int[][] dp = new int[N][k+1]
among dp[i][j] Express [0...i] Scope transactions j What's the biggest benefit you get at this time . If I could dp Fill out this two-dimensional form , Then the return dp[N-1][k] The value of is the answer to the question .
dp In this two-dimensional matrix ,
The value in the first row represents the array [0..0] Within the scope of , The maximum return of several transactions , obviously , All are 0.
The value of the first column of the array [0...i] Within the scope of , transaction 0 The biggest gain at this time , obviously , All of them are 0.
For any common location dp[i][j] Value ,
We can enumerate i Whether the location is involved in the transaction , If i Location does not participate in the transaction , that dp[i][j] = dp[i-1][j], If i Position participation in the transaction , that i The position must be the last time to sell .
The last time to buy , It can be as follows ：
The last time to buy is i Location , that dp[i][j] = dp[i][j-1] - arr[i] + arr[i]
The last time to buy is i-1 Location , that dp[i][j] = dp[i-1][j-1] - arr[i-1] + arr[i]
The last time to buy is i-2 Location , that dp[i][j] = dp[i-2][j-1] - arr[i-2] + arr[i]
...
The last time to buy is 0 Location , that dp[i][j] = dp[0][j-1] - arr[0] + arr[i]
// i Location does not participate in the transaction , be dp[i][j] At least dp[i-1][j]
dp[i][j] = dp[i - 1][j];
for (int m = 0; m <= i; m++) {
// Enumerate the timing of each purchase
dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i] , dp[i][j]);
}
The complete code is as follows ：
public class LeetCode_0188_BestTimeToBuyAndSellStockIV {
public static int maxProfit(int k, int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int N = arr.length;
if (k >= N >> 1) {
return infinityMax(arr);
}
int[][] dp = new int[N][k + 1];
for (int i = 1; i < N; i++) {
for (int j = 1; j <= k; j++) {
// i Location does not participate in the transaction , be dp[i][j] At least dp[i-1][j]
dp[i][j] = dp[i - 1][j];
for (int m = 0; m <= i; m++) {
// Enumerate the timing of each purchase
dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i], dp[i][j]);
}
}
}
return dp[N - 1][k];
}
public static int infinityMax(int[] arr) {
int ans = 0;
for (int i = 1; i < arr.length; i++) {
ans += Math.max(arr[i] - arr[i - 1], 0);
}
return ans;
}
}
The above code contains an enumeration behavior
dp[i][j] = dp[i - 1][j] + arr[i] - arr[i];
for (int m = 0; m <= i; m++) {
// Enumerate the timing of each purchase
dp[i][j] = Math.max(dp[m][j - 1] - arr[m] + arr[i], dp[i][j]);
}
Increased time complexity , We can optimize this enumeration .
We can give a specific example to illustrate how to optimize ,
such as ,
When we ask for dp[5][3] This value , We can enumerate 5 Whether the location is involved in the transaction , hypothesis 5 Location does not participate in the transaction , that dp[5][3] = dp[4][3], hypothesis 5 Position participation in the transaction , that 5 The position must be the last time to sell . The last time to buy , It can be as follows ：
The last time to buy is 5 Location , that dp[5][3] = dp[5][2] - arr[5] + arr[5]
The last time to buy is 4 Location , that dp[5][3] = dp[4][2] - arr[4] + arr[5]
The last time to buy is 3 Location , that dp[5][3] = dp[3][2] - arr[3] + arr[5]
The last time to buy is 2 Location , that dp[5][3] = dp[2][2] - arr[2] + arr[5]
The last time to buy is 1 Location , that dp[5][3] = dp[1][2] - arr[1] + arr[5]
The last time to buy is 0 Location , that dp[5][3] = dp[0][2] - arr[0] + arr[5]
We ask dp[4][3] This value , We can enumerate 4 Whether the location is involved in the transaction , hypothesis 4 Location does not participate in the transaction , that dp[4][3] = dp[3][3], hypothesis 4 Position participation in the transaction , that 4 The position must be the last time to sell . The last time to buy , It can be as follows ：
The last time to buy is 4 Location , that dp[4][3] = dp[4][2] - arr[4] + arr[4]
The last time to buy is 3 Location , that dp[4][3] = dp[3][2] - arr[3] + arr[4]
The last time to buy is 2 Location , that dp[4][3] = dp[2][2] - arr[2] + arr[4]
The last time to buy is 1 Location , that dp[4][3] = dp[1][2] - arr[1] + arr[4]
The last time to buy is 0 Location , that dp[4][3] = dp[0][2] - arr[0] + arr[4]
Compare dp[5][3] and dp[4][3] Dependency of , It can be concluded as follows ：
Suppose you're looking for dp[4][3] In the process of , We can get the maximum value of the following recurrence formula
dp[4][2] - arr[4]
dp[3][2] - arr[3]
dp[2][2] - arr[2]
dp[1][2] - arr[1]
dp[0][2] - arr[0]
We define the maximum value of the above formula as best, that
dp[5][3] = Math.max(dp[4][3],Math.max(dp[5][2] - arr[5] + arr[5], best + arr[5]))
therefore dp[5][3] Can be dp[4][3] Accelerate to get ,
Empathy ,
dp[4][3] Can pass dp[3][3] Accelerate to get ,
dp[3][3] Can pass dp[2][3] Accelerate to get ,
dp[2][3] Can pass dp[1][3] Accelerate to get ,
dp[1][3] It can be easily concluded that ,dp[1][3] There are several possibilities :
possibility 1,1 Location is not involved at all , be
int p1 = dp[0][3]
possibility 2,1 Position as the last selling opportunity , The buying opportunity is 1 Location
int p2 = dp[1][2] + arr[1] - arr[1]
possibility 3,1 Position as the last selling opportunity , The buying opportunity is 0 Location
int p3 = dp[0][2] + arr[1] - arr[0]
here ,best The value of is
int best = Math.max(p2 - arr[1], p3 - arr[1])
And then through dp[1][3] Speed up dp[2][3], adopt dp[2][3] Speed up dp[3][3]......, So two-dimensional dp The filling method of is to fill in by column ,
Fill in first dp[1][0],dp[1][2] Until dp[1][k], Fill in the first column ;
Then fill in dp[2][0],dp[2][1] Until dp[2][k], Fill in the second column ;
...
Fill in each column in turn , Until you've filled in page N-1 Column .
Enumeration behavior is optimized , The complete code after optimizing enumeration is as follows ：
public class LeetCode_0188_BestTimeToBuyAndSellStockIV {
public static int maxProfit(int k, int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int N = arr.length;
if (k >= N >> 1) {
return infinityMax(arr);
}
int[][] dp = new int[N][k + 1];
for (int j = 1; j <= k; j++) {
int p1 = dp[0][j];
int best = Math.max(dp[1][j - 1] - arr[1], dp[0][j - 1] - arr[0]);
dp[1][j] = Math.max(p1, best + arr[1]);
for (int i = 2; i < N; i++) {
p1 = dp[i - 1][j];
best = Math.max(dp[i][j - 1] - arr[i], best);
dp[i][j] = Math.max(p1, best + arr[i]);
}
}
return dp[N - 1][k];
}
public static int infinityMax(int[] arr) {
int ans = 0;
for (int i = 1; i < arr.length; i++) {
ans += Math.max(arr[i] - arr[i - 1], 0);
}
return ans;
}
}
LeetCode 123. The best time to buy and sell stocks III
Main idea ： In the last question , Make k=2 Is the answer to this question .
LeetCode 309. The best time to buy and sell stocks includes the freezing period
Main idea ： Because of the freezing period , So there are three states of each position ：
-
Freezing period
-
Hold shares
-
Do not hold shares , Not in the freezing period
Define three arrays , respectively i What is the maximum value of the position in these three cases
// In the freezing period
int[] cooldown = new int[N];
// Hold shares
int[] withStock = new int[N];
// Do not hold shares , It's not frozen
int[] noStock = new int[N];
Obviously, there are the following conclusions ：
// 0 The location needs to be frozen , explain 0 The location is bought and sold , The payoff is 0
cooldown[0] = 0;
// 0 Position requires holding shares , Only possible in 0 Position bought a share , At this time, the income is 0-arr[0]
withStock[0] = -arr[0];
// 0 Position no stock , Not in the freezing period , Description in 0 No decision was made about location . At this time, the income is also 0
noStock[0] = 0;
For a common location i
// If i The location should be in the freezing period , Then the previous position must hold shares , And sell in the current position , be in cooldown state
cooldown[i] = withStock[i - 1] + arr[i];
// If i Position to hold shares , Then the previous position can hold shares , To the current location without making a decision , Or there are no stocks in the previous position , Buy a share in the current position
withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
// If i Position no stock , Then there may be no stock in the previous position , Or the previous position is the freezing period , To the current position, there is no buying action
noStock[i] = Math.max(noStock[i - 1], cooldown[i - 1]);
The maximum benefit is the maximum value of the above three methods . For the full code, see ：
public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown {
public static int maxProfit(int[] arr) {
if (arr.length < 2) {
return 0;
}
int N = arr.length;
// In the freezing period
int[] cooldown = new int[N];
// Hold shares
int[] withStock = new int[N];
// Do not hold shares , It's not frozen
int[] noStock = new int[N];
cooldown[0] = 0;
withStock[0] = -arr[0];
noStock[0] = 0;
for (int i = 1; i < arr.length; i++) {
withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
cooldown[i] = withStock[i - 1] + arr[i];
noStock[i] = Math.max(noStock[i - 1], cooldown[i - 1]);
}
return Math.max(cooldown[N - 1], Math.max(withStock[N - 1], noStock[N - 1]));
}
}
Because the three arrays have a recursive relationship , So you can replace three arrays with three variables , Do space compression , The optimized code is as follows ：
public class LeetCode_0309_BestTimeToBuyAndSellStockWithCooldown {
// Space compressed version
public static int maxProfit(int[] arr) {
if (arr.length < 2) {
return 0;
}
// In the freezing period
int cooldown = 0;
// Hold shares
int withStock = -arr[0];
// Do not hold shares , It's not frozen
int noStock = 0;
for (int i = 1; i < arr.length; i++) {
int next1 = Math.max(withStock, noStock - arr[i]);
int next2 = withStock + arr[i];
int next3 = Math.max(noStock, cooldown);
withStock = next1;
cooldown = next2;
noStock = next3;
}
return Math.max(cooldown, Math.max(withStock, noStock));
}
}
LeetCode 714. The best time to buy and sell stocks includes handling fees
Main idea ： Since there is no freezing period , So in i In position , There are only two states
// withStock[i] Express ：i Position with stock , The biggest gain
int[] withStock = new int[arr.length];
// noStock[i] Express ：i Position without stock , The biggest gain
int[] noStock = new int[arr.length];
in the light of 0 Location
// 0 Position holding shares , The biggest gain , Can only be 0 Position to buy a share
withStock[0] = -arr[0];
// 0 Position does not hold shares , The biggest gain , Can only be 0 Position does not trade , Yield is 0, If 0 Position trading , The benefit is (0 - arr[i] + arr[i] - fee), Obviously less than 0
noStock[0] = 0;
For general locations i
// i Location requires stock , explain i The position of the stock can be i-1 The position has not been obtained by trading until now , It can also be i-1 Position no stock , Buy the current stock and get
withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
// i Position no stock , explain i The position of the stock can be determined by i-1 There are stocks in the position. Sell one stock at the current position （ Including handling charges ）, It can also be the maximum return without stocks in the previous position
noStock[i] = Math.max(withStock[i - 1] + arr[i] - fee, noStock[i - 1]);
The complete code is as follows ：
public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee {
public static int maxProfit1(int[] arr, int fee) {
if (arr.length < 2) {
return 0;
}
int[] withStock = new int[arr.length];
int[] noStock = new int[arr.length];
// Hold shares
withStock[0] = -arr[0];
// Do not hold shares
noStock[0] = 0;
for (int i = 1; i < arr.length; i++) {
withStock[i] = Math.max(withStock[i - 1], noStock[i - 1] - arr[i]);
noStock[i] = Math.max(withStock[i - 1] + arr[i] - fee, noStock[i - 1]);
}
return Math.max(withStock[arr.length - 1], noStock[arr.length - 1]);
}
}
alike , Both arrays have a recursive relationship , Can do space compression , The simplified code is as follows ：
public class LeetCode_0714_BestTimeToBuyAndSellStockWithTransactionFee {
public static int maxProfit(int[] arr, int fee) {
if (arr.length < 2) {
return 0;
}
// Hold shares
int withStock = -arr[0];
// Do not hold shares
int noStock = 0;
for (int i = 1; i < arr.length; i++) {
int next1 = Math.max(withStock, noStock - arr[i]);
int next3 = Math.max(withStock + arr[i] - fee, noStock);
withStock = next1;
noStock = next3;
}
return Math.max(withStock, noStock);
}
}
more
Algorithm and data structure notes
Reference material
Algorithm and data structure architecture class - Zuo Chengyun
![[NLP] HMM hidden Markov + Viterbi word segmentation](/img/9a/b39a166320c2f2001f10913f789c90.png)