Stock problems 5 times

---

121. The best time to buy and sell stocks

Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price .

You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

Only one transaction can be made ,
0 Time is the selling opportunity for this transaction , How much money can I make
1 Time is the selling opportunity for this transaction , How much money can I make
2 Time is the selling opportunity for this transaction , How much money can I make
3 Time is the selling opportunity for this transaction , How much money can I make
…
seek max
That's the answer.

Code

class Solution {
    
    public int maxProfit(int[] prices) {
    
		if (prices==null||prices.length==0) {
    
			return 0;
		}
		
		int min=prices[0];
        int ans=0;
        for(int i=1;i<prices.length;i++){
    
            ans=Math.max(ans,prices[i]-min);
            min=Math.min(min,prices[i]);
        }
        return ans;
    }
}

122. The best time to buy and sell stocks II

Give you an array of integers prices , among prices[i] Represents a stock i Sky price .

Every day , You can decide whether to buy and / Or sell shares . You at any time most Can only hold A wave of Stocks . You can also buy... First , And then in On the same day sell .

return What you can get Maximum profits .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

Imagine that the whole stock market is equivalent to a peak and trough chart . Since he has unlimited trading , You count every climb as a money , All add up to the answer .
All the climbing money is accumulated , It is equivalent to grasping every market

i The number of positions minus the number before
Less than zero means that the case management is 0
If it is greater than zero, it will be included in the answer , It turns the process of finding and climbing into the process of subtracting two adjacent numbers .

Code

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int n=prices.length;
        if(prices==null||n==0){
    
            return 0;
        }
        int ans=0;
        for(int i=1;i<n;i++){
    
            ans+=(prices[i]-prices[i-1])>0?prices[i]-prices[i-1]:0;
        }
        return ans;
    }
}

188. The best time to buy and sell stocks IV

Given an array of integers prices , It's the first i Elements prices[i] Is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most k transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

If the maximum number of transactions K>=N/2, Equal to unlimited number of transactions , Equivalent to the stock problem 2

A length of N In the array , Climb the most N/2

Keep climbing : Multiple transactions have the same effect as one transaction

If not more than N/2
From left to right + Business restrictions

dp[i][j]: Only in arr 0…i Make a deal on the Internet , And the number of transactions should not exceed j The biggest gain at this time
The bottom right corner is the answer

0 That's ok , 0 Fill in all columns 0
0 Bank representative 0 Shares , do j transaction
0 Column represents 0 transaction

General position dp[8][3]

Possibility division ,8 Do you want to participate in the transaction
1)8 Location does not participate :dp[7][3]

2)8 Position to participate in the transaction , It can only be the selling opportunity of the last transaction
8 Location participation , What was the last transaction ?
The possibility of buying time for the last transaction :

1)8 Position buy

2)7 Position buy

All the possibilities
0 To 8, transaction 2 Time

Slope optimization

dp[5][2]

dp[6][2]

stay dp[5][2] in
Change the enumerated number into

From left to right , Fill in the form from top to bottom

Code

class Solution {
    
    public static int allTrans(int[] prices) {
    
		int ans = 0;
		for (int i = 1; i < prices.length; i++) {
    
			ans += Math.max(prices[i] - prices[i - 1], 0);
		}
		return ans;
	}
    public int maxProfit(int k, int[] prices) {
    
        int n=prices.length;
        if(prices==null||n==0){
    
            return 0;
        }
        if(k>=n/2){
    
            return allTrans(prices);
        }
        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]-prices[1],dp[0][j-1]-prices[0]);
            dp[1][j]=Math.max(p1,best+prices[1]);
            for(int i=1;i<n;i++){
    
                p1=dp[i-1][j];
                best=Math.max(best,dp[i][j-1]-prices[i]);
                dp[i][j]=Math.max(p1,best+prices[i]);
            }
        }
        return dp[n-1][k];
    }
}

123. The best time to buy and sell stocks III

Given an array , It's the first i An element is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most Two pens transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

With the stock problem 4, Look back at the stock problem 3 It's much simpler
Just put k Turn into 2 nothing more

Code

class Solution {
    
    public int maxProfit(int[] prices) {
    
        if(prices==null||prices.length<2){
    
            return 0;
        }
        int min=prices[0];
        //  Finish one transaction and buy the second stock 
        int onceBuyAndsell=-prices[0];
        //  Finish the first transaction 
        int onceBuyMax=0;
        int ans=0;
        for(int i=1;i<prices.length;i++){
    
            ans=Math.max(ans,onceBuyAndsell+prices[i]);
            min=Math.min(min,prices[i]);
            onceBuyMax=Math.max(onceBuyMax,prices[i]-min);
            onceBuyAndsell=Math.max(onceBuyAndsell,onceBuyMax-prices[i]);
        }
        return ans;
    }
}

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

Given an array of integers prices, Among them the first prices[i] It means the first one i Day's share price .​

Design an algorithm to calculate the maximum profit . Under the following constraints , You can do as many deals as you can （ Buy and sell a stock many times ）:

After sale of shares , You can't buy shares the next day ( That is, the freezing period is 1 God ).
Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

Define new indicators buy[22]
0~22 Income from unlimited transactions minus a relatively good buying opportunity , The best way to integrate is buy[22]
This combined rightmost gain is finally added 100 Namely 0~23 Get the optimal return of unlimited transactions in the range

0) The last transaction must be in 0 Position buy ,0~0 Subtract... From the money obtained from unlimited transactions on the range 0 Buying price of position , Then add 5 The selling price of the position
1) The last transaction must be in 1 Position buy ,0~1 Subtract... From the money obtained from unlimited transactions on the range 1 Add... At the end of the buying price of the position 5 The selling price of the position
2) The last transaction must be in 2 Position buy ,0~2 Subtract... From the money obtained from unlimited transactions on the range 2 Buying price of position , Then add 5 The selling price of the position
3) The last transaction must be in 3 Position buy , 0~3 Subtract... From the money obtained from unlimited transactions on the range 3 Buying price of position , Then add 5 The selling price of the position
The overall optimization is not to add 5 The previous part of the position , All consider which is the best
The last operation must be buying action

buy[i]:

Refer to 0 To i On the scope of , The last operation must be buying

1) No participation , be not in i Position buy

2) i Participate in , because cooldown, So it was 0~i-2 The money obtained from unlimited transactions in the range

sell[i]

0~i Make unlimited transactions , The last action must be selling , Get the best income

1) No participation , sell[i]= sell[i-1]

2) i Participate in ,
i It's the last time to sell
Namely 0~i-1 Consider the comprehensive unlimited income in scope , And an optimal buying price , Plus you at this time i The value of the location

Code

	public static int maxProfit(int[] prices) {
    
		if (prices.length < 2) {
    
			return 0;
		}
		int N = prices.length;
		int[] buy = new int[N];
		int[] sell = new int[N];
		// buy[0]  You don't have to set it  buy[0] = -arr[0]
		// sell[0] = 0
		buy[1] = Math.max(-prices[0], -prices[1]);
		sell[1] = Math.max(0, prices[1] - prices[0]);
		for (int i = 2; i < N; i++) {
    
			buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
			sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
		}
		return sell[N - 1];
	}

Space compression

	public static int maxProfit(int[] prices) {
    
		if (prices.length < 2) {
    
			return 0;
		}
		int buy1 = Math.max(-prices[0], -prices[1]);
		int sell1 = Math.max(0, prices[1] - prices[0]);
		int sell2 = 0;
		for (int i = 2; i < prices.length; i++) {
    
			int tmp = sell1;
			sell1 = Math.max(sell1, buy1 + prices[i]);
			buy1 = Math.max(buy1, sell2 - prices[i]);
			sell2 = tmp;
		}
		return sell1;
	}

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

Given an array of integers prices, among prices[i] It means the first one i Day's share price ; Integers fee Represents the handling fee for trading shares .

You can close the deal indefinitely , But you have to pay a handling fee for every transaction . If you have bought a stock , You can't buy any more stock until you sell it .

Return the maximum profit .

Be careful ： A deal here refers to the whole process of buying, holding and selling stocks , You only need to pay a handling fee for each transaction .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

Similar to the previous question
buy:0 To i The best time to buy
sell:0 To i The best time to sell

Code

	public static int maxProfit(int[] arr, int fee) {
    
		if (arr == null || arr.length < 2) {
    
			return 0;
		}
		int N = arr.length;
		// 0..0 0 -[0] - fee
		int bestbuy = -arr[0] - fee;
		// 0..0  sell  0
		int bestsell = 0;
		for (int i = 1; i < N; i++) {
    
			//  Came to i It's in place ！
			//  If in i Have to buy   income  -  trade price  - fee
			int curbuy = bestsell - arr[i] - fee;
			//  If in i Must sell   The overall best （ income  -  Good wholesale price  - fee）
			int cursell = bestbuy + arr[i];
			bestbuy = Math.max(bestbuy, curbuy);
			bestsell = Math.max(bestsell, cursell);
		}
		return bestsell;
	}