Best Time To Buy And Sell Stock Iii

                                            
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = INT_MIN, sell1 = 0, buy2 = INT_MIN, sell2 = 0;
        
        for(int price : prices) {
            buy1 = max(buy1, -price);
            sell1 = max(sell1, buy1 + price);
            buy2 = max(buy2, sell1 - price);
            sell2 = max(sell2, buy2 + price);
        }
        
        return sell2;
    }
};

                                            
class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE;
        int buy2 = Integer.MIN_VALUE;
        int sell1 = 0;
        int sell2 = 0;
        
        for (int price : prices) {
            buy1 = Math.max(buy1, -price);
            sell1 = Math.max(sell1, buy1 + price);
            buy2 = Math.max(buy2, sell1 - price);
            sell2 = Math.max(sell2, buy2 + price);
        }
        
        return sell2;
    }
}

                                            
class Solution(object):
    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0
        
        first_buy = float('-inf')
        first_sell = 0
        second_buy = float('-inf')
        second_sell = 0
        
        for price in prices:
            first_buy = max(first_buy, -price)
            first_sell = max(first_sell, first_buy + price)
            second_buy = max(second_buy, first_sell - price)
            second_sell = max(second_sell, second_buy + price)
        
        return second_sell

                                            
int maxProfit(int* prices, int pricesSize) {
    int buy1 = INT_MIN, sell1 = 0;
    int buy2 = INT_MIN, sell2 = 0;
    
    for (int i = 0; i < pricesSize; i++) {
        buy1 = fmax(buy1, -prices[i]);
        sell1 = fmax(sell1, buy1 + prices[i]);
        buy2 = fmax(buy2, sell1 - prices[i]);
        sell2 = fmax(sell2, buy2 + prices[i]);
    }
    
    return sell2;
}

                                            
public class Solution {
    public int MaxProfit(int[] prices) {
        int n = prices.Length;
        if (n == 0) return 0;
        
        int firstBuy = Int32.MinValue;
        int firstSell = 0;
        int secondBuy = Int32.MinValue;
        int secondSell = 0;
        
        for (int i = 0; i < n; 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;
    }
}

                                            
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let firstBuy = Infinity, secondBuy = Infinity;
    let firstSell = 0, secondSell = 0;
    
    for (let price of prices) {
        firstBuy = Math.min(firstBuy, price);
        firstSell = Math.max(firstSell, price - firstBuy);
        secondBuy = Math.min(secondBuy, price - firstSell);
        secondSell = Math.max(secondSell, price - secondBuy);
    }
    
    return secondSell;
};

                                            
function maxProfit(prices: number[]): number {
    let buy1 = Infinity, buy2 = Infinity;
    let sell1 = 0, sell2 = 0;
    
    for (let price of prices) {
        buy1 = Math.min(buy1, price);
        sell1 = Math.max(sell1, price - buy1);
        buy2 = Math.min(buy2, price - sell1);
        sell2 = Math.max(sell2, price - buy2);
    }
    
    return sell2;
};

                                            
class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $n = count($prices);
        $buy1 = $buy2 = PHP_INT_MAX;
        $sell1 = $sell2 = 0;
        
        for ($i = 0; $i < $n; $i++) {
            $buy1 = min($buy1, $prices[$i]);
            $sell1 = max($sell1, $prices[$i] - $buy1);
            $buy2 = min($buy2, $prices[$i] - $sell1);
            $sell2 = max($sell2, $prices[$i] - $buy2);
        }
        
        return $sell2;
    }
}

                                            
class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var buy1 = Int.min
        var buy2 = Int.min
        var sell1 = 0
        var sell2 = 0
        
        for price in prices {
            buy1 = max(buy1, -price)
            sell1 = max(sell1, buy1 + price)
            buy2 = max(buy2, sell1 - price)
            sell2 = max(sell2, buy2 + price)
        }
        
        return sell2
    }
}

                                            
class Solution {
    fun maxProfit(prices: IntArray): Int {
        var buy1 = Int.MIN_VALUE
        var sell1 = 0
        var buy2 = Int.MIN_VALUE
        var sell2 = 0
        for (price in prices) {
            buy1 = maxOf(buy1, -price)
            sell1 = maxOf(sell1, buy1 + price)
            buy2 = maxOf(buy2, sell1 - price)
            sell2 = maxOf(sell2, buy2 + price)
        }
        return sell2
    }
}

                                            
class Solution {
  int maxProfit(List<int> prices) {
    if (prices.isEmpty) {
      return 0;
    }
    
    int n = prices.length;
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    
    for (int i = 1; i < n; i++) {
      buy1 = buy1 > -prices[i] ? buy1 : -prices[i];
      sell1 = sell1 > buy1 + prices[i] ? sell1 : buy1 + prices[i];
      buy2 = buy2 > sell1 - prices[i] ? buy2 : sell1 - prices[i];
      sell2 = sell2 > buy2 + prices[i] ? sell2 : buy2 + prices[i];
    }
    
    return sell2;
  }
}

                                            
func maxProfit(prices []int) int {
    n := len(prices)
    if n == 0 {
        return 0
    }

    K := 2
    dp := make([][]int, K+1)
    for i := 0; i <= K; i++ {
        dp[i] = make([]int, n)
    }

    for k := 1; k <= K; k++ {
        maxPrev := -prices[0]
        for i := 1; i < n; i++ {
            dp[k][i] = max(dp[k][i-1], prices[i]+maxPrev)
            maxPrev = max(maxPrev, dp[k-1][i]-prices[i])
        }
    }

    return dp[K][n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
object Solution {
    def maxProfit(prices: Array[Int]): Int = {
        val n = prices.length
        var buy1 = Int.MaxValue
        var sell1 = 0
        var buy2 = Int.MaxValue
        var sell2 = 0
        for (i <- 0 until n) {
            buy1 = buy1.min(prices(i))
            sell1 = sell1.max(prices(i) - buy1)
            buy2 = buy2.min(prices(i) - sell1)
            sell2 = sell2.max(prices(i) - buy2)
        }
        sell2
    }
}

                                            
impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut buy1 = i32::MAX;
        let mut buy2 = i32::MAX;
        let mut sell1 = 0;
        let mut sell2 = 0;
        
        for price in prices {
            buy1 = buy1.min(price);
            sell1 = sell1.max(price - buy1);
            buy2 = buy2.min(price - sell1);
            sell2 = sell2.max(price - buy2);
        }
        
        sell2
    }
}

To solve this coding challenge, we need to carefully analyze the problem requirements and constraints: we can perform at most two transactions, which means we can buy and sell the stock up to two times. Our goal is to maximize our profit from these transactions. Let's break down how to approach this problem step-by-step and represent it in pseudocode with detailed explanations and comments.

Explanation

Initialization : We need four variables to manage our profits:

first_buy

: This will keep track of the maximum profit when we buy the stock the first time.
first_sell

: This will store the maximum profit after selling the stock the first time.
second_buy

: This will keep track of the maximum profit after buying the stock the second time.
second_sell

: This will store the maximum profit after selling the stock the second time.

Initially, set

first_buy

and

second_buy

to negative infinity because when we buy a stock, the profit is negative, and a very large negative value ensures it gets updated correctly with the first price we encounter.

first_sell

and

second_sell

should be initialized to 0 because we start with zero profit.

Iterate through Prices : We iterate through the list of prices and update our four variables to track the maximum possible profits at each price:

Update
first_buy

to the maximum of its current value and the negative price of the current day (because buying decreases profit).
Update
first_sell

to the maximum of its current value and the profit we would have if we sold the stock today (i.e., the sum of
first_buy

and today's price).
Update
second_buy

to the maximum of its current value and the profit we would have after selling once and then buying again (i.e., the difference between
first_sell

and today's price).
Update
second_sell

to the maximum of its current value and the profit we would have if we sold the stock after the second buy (i.e., the sum of
second_buy

and today's price).

Return Result : After iterating through all the price values,
second_sell

will contain the maximum profit achievable with at most two transactions.

Detailed Steps in Pseudocode

                                            
# Initialize variables
first_buy = negative infinity   # Maximum profit after first buy
first_sell = 0                  # Maximum profit after first sell
second_buy = negative infinity  # Maximum profit after second buy
second_sell = 0                 # Maximum profit after second sell

# Iterate through the prices list
for each price in prices:
    # Update the maximum profit after the first buy
    first_buy = max(first_buy, -price)

    # Update the maximum profit after the first sell
    first_sell = max(first_sell, first_buy + price)
    
    # Update the maximum profit after the second buy
    second_buy = max(second_buy, first_sell - price)
    
    # Update the maximum profit after the second sell
    second_sell = max(second_sell, second_buy + price)

# The second_sell contains the maximum profit achievable with at most two transactions
return second_sell

Explanation

By following these steps, we ensure that we:

Capture the most profitable opportunity for the first transaction.
Correctly account for the impact of potential second transactions.
Ultimately return the best possible profit after two transactions, considering all price changes in the given list.

Let's walk through an example

Given

prices = [3, 3, 5, 0, 0, 3, 1, 4]

Initialize variables:

first_buy = -inf

,
first_sell = 0

,
second_buy = -inf

,
second_sell = 0

Iterate through prices:

For price = 3:

first_buy = max(-inf, -3) = -3
first_sell = max(0, -3 + 3) = 0
second_buy = max(-inf, 0 - 3) = -3
second_sell = max(0, -3 + 3) = 0

For price = 3 (second time):

first_buy = max(-3, -3) = -3
first_sell = max(0, -3 + 3) = 0
second_buy = max(-3, 0 - 3) = -3
second_sell = max(0, -3 + 3) = 0

Continue this process for all prices...

Eventually:

For price = 1:

second_sell = max(6, 2 + 1) = 6

Thus, the maximum profit is

6

after considering two transactions. Through this detailed approach, we ensure that each variable is updated logically to reflect the highest possible profit at every step in the process.