Leetcode Best Time to Buy and Sell Stock series topic analysis and java implementation

Leetcode Best Time to Buy and Sell Stock series topic analysis and java implementation

The title of this series is to allow us to trade according to restrictions in a continuous period of stock prices to maximize profits. Each derivative title will set some restrictions

  • Best Time to Buy and Sell Stock I
  • Best Time to Buy and Sell Stock II
  • Best Time to Buy and Sell Stock III
  • Best Time to Buy and Sell Stock with Cooldown
  • Best Time to Buy and Sell Stock with Transaction Fee

Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

This question limits the number of times we buy and sell, so we need to find a way to buy at the lowest point and sell at the highest point. However, there is a limitation that the selling time must be after buying, so we can't directly find the difference between the maximum value and the minimum value, but we can use a variable to save the front minimum value of the current scanned value, and then calculate the difference with the current value, If greater than the historical maximum, update the maximum

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

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

This question does not limit the total number of transactions, so we can use the greedy algorithm. As long as i is higher than the price of i-1 day, we will buy on i-1 day and sell on i-1 day to obtain all possible profits.

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

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

The difficulty of this question has increased slightly, because we are only allowed to buy and sell twice, and we can only hold one at the same time, that is, the interval of the two transactions cannot coincide. So we divided this question into two parts
prices[0:n-1] => prices[0:i] + prices[i:n-1]
The method in I is used to calculate the maximum profit of each section. We first calculate the maximum profit on day I from left to right, calculate it once from right to left, and then add it up for statistics. We can know the maximum profit that can be obtained by dividing day n

class Solution{
	public int maxProfit(int[] prices){
		if(prices == null || prices.length == 0){
			return 0;
		}
		int[] leftProfit = new int[prices.length];
		int leftMin = 0; int leftMaxProfit = 0;
		for(int i = 1; i < prices.length;i ++){
			leftMin = Math.min(leftMin,prices[i];
			leftMaxProfit = Math.max(prices[i]-leftMin,leftMaxProfit);
			leftProfit[i] =  leftMaxProift;
		}
		int[] rightProfit = new int[prices.length];
		int rightMax = prices[prices.length-1],rightMaxProfit = 0;
		int res = 0;
		for(int i = prices.length-2;i >=0;i--){
			rightMax = Math.max(rightMax,prices[i];
			rightMaxProfit = Math.max(rightMax-prices[i],rightMaxProfit);
			rightProfit[i] = rightMaxProfit;
			res = Math.max(res,leftProfit[i]+rightProfit[i]);
		}
		return res;
	}
}

Best Time to Buy and Sell Stock with Cooldown

This question is also a little difficult. Although there is no limit on the number of times we buy and sell, we can't buy it the next day after selling.

Similarly, we also use dynamic programming to solve this problem. We use two arrays to store the maximum benefit if we sell or don't sell on day i, and then find the two maxima at the end.
We are also two arrays. If we hold them on day i, there are only two possibilities. Either i hold them on day i-1 or i buy them on day i.
If i don't hold it on day i, i either sell it on day i, or i don't hold it in day i-1. But if i sell it on day i-1, i'm not allowed to buy it on day i, so i have to hold it on day i-2. So let's see how to do this problem
This question is for reference https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems Solution in.

class Solution{
	int maxProfit_with_cool(int[] prices) {
    	int n = prices.length;
    	int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    	int dp_pre_0 = 0; // For dp[i-2][0]
    	for (int i = 0; i < n; i++) {
        	int temp = dp_i_0;
        	dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        	dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        	dp_pre_0 = temp;
    	}
    	return dp_i_0;
	}
}

Best Time to Buy and Sell Stock with Transaction Fee

There is one difference in this question, that is, a handling fee will be charged for each transaction, which is not much different from that before

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1 = Math.max(dp_i_1,temp-prices[i]-fee);
        }
        return dp_i_0;
    }
}

Tags: Java Algorithm leetcode Interview

Posted by Karlos2394 on Sun, 22 May 2022 21:32:50 +0300