Question 1:
Given an array of ， prices, its ， I ， th element ， prices[i] represents the price of a given stock on ， I ， day.
You can only choose to buy this stock one day and sell it on a different day in the future. Design an 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.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6). 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.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: in this case, no transaction is completed, so the maximum profit is 0.
Tips:
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
1 class Solution { 2 public int maxProfit(int[] prices) { 3 //s1 Means there are shares, s0 No stock 4 int s1=-Integer.MIN_VALUE,s0=0; 5 for (int x:prices) { 6 s1=Math.max(s1,-x); 7 //You can only buy once, so if you have stocks, it must be-x maximal 8 s0=Math.max(s0,s1+x); 9 //Either continue not to buy or sell 10 //System.out.println(s1+" "+s0); 11 } 12 return s0; 13 } 14 }
Idea: for simple dynamic planning, it should be noted that it can only be traded once.
Question 2:
Given an array ， prices, where ， prices[i] represents the price of the stock on ， I ， day.
On each day, you may decide to buy and / or sell shares. You can only hold at most one} share at any time. You can also buy it and sell it on the same day.
Return the # maximum profit you can make.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: if you buy on the second day (stock price = 1) and sell on the third day (stock price = 5), this exchange can make a profit = 5-1 = 4. Then, buy on the 4th day (stock price = 3) and sell on the 5th day (stock price = 6). This exchange can make a profit = 6-3 = 3.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: if you buy on the first day (stock price = 1) and sell on the fifth day (stock price = 5), this exchange can make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them. Because this is involved in multiple transactions at the same time, you must sell the previous shares before buying again.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: in this case, no transaction is completed, so the maximum profit is 0.
Tips:
- 1 <= prices.length <= 3 * 104
- 0 <= prices[i] <= 104
1 class Solution { 2 public int maxProfit(int[] prices) { 3 int s0=0,s1=-Integer.MIN_VALUE; 4 for (int x:prices){ 5 int t0=-Integer.MIN_VALUE,t1=-Integer.MIN_VALUE; 6 t1=Math.max(s1,s0-x); 7 //The difference is that you can trade multiple times, s1 Probably by s0 Convert 8 t0=Math.max(s0,s1+x); 9 s1=Math.max(s1,t1); 10 s0=Math.max(s0,t0); 11 } 12 return s0; 13 } 14 }
Idea: like the first question, the difference is that it is not a transaction. The calculation of s1 is slightly different, and intermediate variables are needed to judge the maximum value.
Question 3:
Give an integer array prices, where the ， prices[i] represents the stock price on the ， I ， day.
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:
- After selling stocks, you can't buy stocks the next day (i.e. the freezing period is 1 day).
Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
Example 1:
Input: prices = [1,2,3,0,2] Output: 3 Explanation: the corresponding transaction status is: [buy, sell, frozen period, buy, sell]
Example 2:
Input: prices = [1] Output: 0
Tips:
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
1 class Solution { 2 public int maxProfit(int[] prices) { 3 //dp[i][0]The first i God, there are no stocks dp[i][1] Have stock 4 //dp[i][0]=max(dp[i-1][0],dp[i-1][0]+x) No stocks yesterday, no stocks today, or tickets sold today 5 //dp[i][1]=max(dp[i-1][1],dp[i-2][0]-x) Yesterday, today, or the day before yesterday 6 // Buy it today, but you can't sell it yesterday, and there were no stocks the day before yesterday 7 int n=prices.length; 8 int[][] dp=new int[n][2]; 9 for (int i=0;i<n;i++) dp[i][1]=-Integer.MIN_VALUE/2; 10 dp[0][1]=-prices[0]; 11 for (int i=1;i<n;i++) { 12 dp[i][0]=Math.max(dp[i][0],Math.max(dp[i-1][0],dp[i-1][1]+prices[i])); 13 if (i<2) { 14 dp[i][1]=Math.max(dp[i-1][1],-prices[i]); 15 }else dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i]); 16 //System.out.println(dp[i][0]+" "+dp[i][1]); 17 } 18 return dp[n-1][0]; 19 } 20 }
See notes for specific ideas.
Question 4:
Given an integer array ， prices, where the ， i ， element represents the stock price on the ， i ， day; The integer ， fee ， represents the handling fee for trading stocks.
You can complete transactions indefinitely, but you need to pay a handling fee for each transaction. If you have bought a stock, you can't continue to buy it until you sell it.
Returns the maximum profit.
Note: a transaction here refers to the whole process of buying, holding and selling stocks. You only need to pay a handling fee for each transaction.
Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: maximum profit that can be achieved:
Buy here {prices[0] = 1
Sell here prices[3] = 8
Buy here prices[4] = 4
Sell here prices[5] = 9
Total profit: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3 Output: 6
Tips:
- 1 <= prices.length <= 5 * 104
- 1 <= prices[i] < 5 * 104
- 0 <= fee < 5 * 104
1 class Solution { 2 public int maxProfit(int[] prices, int fee) { 3 int s0=0,s1=-Integer.MIN_VALUE/2; 4 for (int x:prices){ 5 int t0=0,t1=-Integer.MIN_VALUE/2; 6 t1=Math.max(s1,s0-x); 7 t0=Math.max(s0,s1+x-fee); 8 s1=Math.max(s1,t1); 9 s0=Math.max(s0,t0); 10 } 11 return s0; 12 } 13 }
Idea: similar to question 2, the difference is that a handling fee is added when selling stocks. Note that MINVALUE may cross the boundary, so take half.