Solution For Best Time To Buy And Sell Stock Iii

The Problem:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Solution:

The problem statement asks us to find the maximum profit that can be obtained from at most two transactions. Let’s take a look at a few scenarios:

1. If there are no prices, return 0.
2. If there are only one or two prices, they cannot be used to make any transactions, so return 0.
3. If there are three or more prices, we need to calculate the maximum profit that can be obtained from two transactions.

We will solve the problem using dynamic programming. Let’s create a 2D array dp where dp[i][j] represents the maximum profit that can be obtained by making j transactions on the first i days of the given prices array. We can fill the dp array in the following way:

1. Initialize the dp array to 0.
2. For each day i, we will calculate the maximum profit that can be obtained by making j transactions on the first i days.
3. We can calculate the profit at each day i and transaction j by finding the maximum of:
   a. The profit from the previous transaction j-1 and the price difference on the current day prices[i].
   b. The profit from the previous day i-1 and the profit on the current day j.
4. Return dp[n-1][2], where n is the length of the prices array.

Let’s take a closer look at step 3. To calculate the profit on the current day j, we can traverse the prices array backwards and find the maximum profit that can be obtained by selling the stock on the current day j and buying it on any previous day k. We can use two variables, sell and buy, to keep track of the maximum profit that can be obtained by selling the stock and buying it on any previous day.

Here is the implementation of the above solution:

“`
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
if(n < 2) return 0;

    vector<vector<int>> dp(n, vector<int>(3));
    for(int j = 1; j <= 2; j++){
        int buy = dp[0][j-1] - prices[0];
        for(int i = 1; i < n; i++){
            dp[i][j] = max(dp[i-1][j], prices[i] + buy);
            buy = max(buy, dp[i][j-1] - prices[i]);
        }
    }
    return dp[n-1][2];
}

};
“`

Time Complexity: O(n), where n is the length of the prices array.

Space Complexity: O(n), where n is the length of the prices array. The space complexity can be further optimized to O(1) by using variables instead of a 2D array.

Step by Step Implementation For Best Time To Buy And Sell Stock Iii

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MAX_VALUE, buy2 = Integer.MAX_VALUE;
        int sell1 = 0, sell2 = 0;
        for (int i = 0; i < prices.length; i++) {
            buy1 = Math.min(buy1, prices[i]);
            sell1 = Math.max(sell1, prices[i] - buy1);
            buy2 = Math.min(buy2, prices[i] - sell1);
            sell2 = Math.max(sell2, prices[i] - buy2);
        }
        return sell2;
    }
}

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Base cases
        if len(prices) in [0, 1]: 
            return 0
        
        # First pass: get the maximum profit from one transaction
        profit = 0
        min_price = prices[0]
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
        
        # Second pass: get the maximum profit from two transactions
        max_price = prices[-1]
        second_profit = 0
        for i in range(len(prices) - 2, -1, -1):
            max_price = max(max_price, prices[i])
            second_profit = max(second_profit, max_price - prices[i])
            profit = max(profit, second_profit + profit)
        
        return profit

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let firstBuy = Infinity, secondBuy = Infinity, firstProfit = 0, secondProfit = 0;
    
    for (let i = 0; i < prices.length; i++) {
        // first buy must happen before first sell
        firstBuy = Math.min(firstBuy, prices[i]);
        firstProfit = Math.max(firstProfit, prices[i] - firstBuy);
        
        // second buy must happen after first sell
        secondBuy = Math.min(secondBuy, prices[i] - firstProfit);
        secondProfit = Math.max(secondProfit, prices[i] - secondBuy);
    }
    
    return secondProfit;
};

class Solution {
public:
    int maxProfit(vector& prices) {
        int hold1 = INT_MIN, hold2 = INT_MIN;
        int release1 = 0, release2 = 0;
        for(int i:prices){                              // Assume we only have 0 money at first
            release2 = max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
            hold2    = max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
            release1 = max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
            hold1    = max(hold1,    -i);          // The maximum if we've just buy  1st stock so far. 
        }
        return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
    }
};

public int MaxProfit(int[] prices)
        {
            int firstBuy = int.MinValue, secondBuy = int.MinValue;
            int firstSell = 0, secondSell = 0;

            for (int i = 0; i < prices.Length; i++)
            {
                firstBuy = Math.Max(firstBuy, -prices[i]);
                firstSell = Math.Max(firstSell, firstBuy + prices[i]);
                secondBuy = Math.Max(secondBuy, firstSell - prices[i]);
                secondSell = Math.Max(secondSell, secondBuy + prices[i]);
            }

            return secondSell;
        }