Best Time to Buy and Sell Stock III

class Solution {
  public:
  int maximumProfit(vector<int>& stockPrices) {
    int minCost1 = INT_MAX, 
        minCost2 = INT_MAX;
    int maxProfit1 = 0,
        maxProfit2 = 0;

    for (int price : stockPrices) {
        minCost1 = min(minCost1, price);
        maxProfit1 = max(maxProfit1, price - minCost1);
        minCost2 = min(minCost2, price - maxProfit1);
        maxProfit2 = max(maxProfit2, price - minCost2);
    }

    return maxProfit2;
  }
};

The provided C++ program is designed to calculate the maximum profit from performing at most two stock transactions. This algorithm offers an optimized approach to solving common stock trading problems where the sequence and timing of purchases and sales significantly impact profit outcomes.

• Understanding the Variables:

  • minCost1 and minCost2 track the minimum costs of the stock for the first and second transactions, respectively.
  • maxProfit1 and maxProfit2 record the best profit achievable from the first and second transactions.

• Algorithm Flow:

  1. Initialize minCost1 and minCost2 to the maximum possible integer value (INT_MAX) to ensure any actual stock price found will be lower, setting an initial buying point.
  2. Similarly, initialize maxProfit1 and maxProfit2 to zero as initially, no transactions have occurred.
  3. Iterate through each stock price in the stockPrices vector.
  4. For each price, update minCost1 to be the minimum of the current minCost1 or the price, capturing the lowest price seen so far for the first buy.
  5. Update maxProfit1 by calculating the maximum of the current maxProfit1 or the difference between the current price and minCost1, thus determining the highest profit possible from the first transaction.
  6. Update minCost2 by calculating the minimum of the current minCost2 or the difference between the current price and maxProfit1, essentially considering the cost of a second buy after realizing the first profit.
  7. Update maxProfit2 by considering the maximum of the current maxProfit2 or the profit from selling at the current price minus minCost2, ensuring the best outcome from two sequential transactions.

• Final Output:

  • The function returns maxProfit2, which represents the highest achievable profit with up to two buy-sell transactions.

This solution efficiently captures the essence of the problem by accurately managing profit calculations through minimal iterations over the data, thus being both time and space efficient.

class Solution {
    public int calculateMaxProfit(int[] stockPrices) {
        int minimumPrice1 = Integer.MAX_VALUE, minimumPrice2 = Integer.MAX_VALUE;
        int maxProfit1 = 0, maxProfit2 = 0;

        for (int price : stockPrices) {
            minimumPrice1 = Math.min(minimumPrice1, price);
            maxProfit1 = Math.max(maxProfit1, price - minimumPrice1);
            minimumPrice2 = Math.min(minimumPrice2, price - maxProfit1);
            maxProfit2 = Math.max(maxProfit2, price - minimumPrice2);
        }

        return maxProfit2;
    }
}

The Java solution provided for calculating the maximum profit that can be achieved from a sequence of stock prices with at most two transactions follows a dynamic approach. Here’s an overview of how the code works:

• Define two variables to keep track of the lowest stock prices (minimumPrice1 and minimumPrice2) initializing them to the maximum possible value an int can take.
• Set two variables (maxProfit1 and maxProfit2) to zero, which track the maximum profits after the first and second transaction, respectively.

During a single pass through the stockPrices array:

• Update minimumPrice1 to the minimum value between the current minimumPrice1 and the current stock price. This keeps track of the lowest price seen so far.
• Calculate maxProfit1 as the maximum of the current maxProfit1 and the difference between the current price and minimumPrice1. This computes the maximum profit possible with one transaction up to the current price.
• Update minimumPrice2 by considering the effective "cost" of buying a second stock, factoring in the profit from the first transaction. This is done by minimizing minimumPrice2 with the difference between the current price and maxProfit1.
• Calculate maxProfit2 as the maximum of the current maxProfit2 and the difference between the current price and minimumPrice2. This examines the profit potential from a second transaction after achieving the first transaction’s max profit.

The function finally returns maxProfit2, representing the highest possible profit with up to two transactions.

int calculateMaxProfit(int* stockPrices, int length) {
    int firstBuyCost = INT_MAX, secondBuyCost = INT_MAX;
    int firstSellProfit = 0, secondSellProfit = 0;
    for (int i = 0; i < length; i++) {
        firstBuyCost = min(firstBuyCost, stockPrices[i]);
        firstSellProfit = max(firstSellProfit, stockPrices[i] - firstBuyCost);
        secondBuyCost = min(secondBuyCost, stockPrices[i] - firstSellProfit);
        secondSellProfit = max(secondSellProfit, stockPrices[i] - secondBuyCost);
    }
    return secondSellProfit;
}

The given C code provides a method to calculate the maximum profit that can be obtained from two transactions on a stock. Here’s how you can understand the mechanism of the function calculateMaxProfit:

• Inputs and Variables Initialization:

  • The function accepts an array stockPrices containing daily stock prices and its length.
  • Variables firstBuyCost and secondBuyCost track the minimum amount spent on buying the stock for the first and second transactions, initialized to INT_MAX.
  • firstSellProfit and secondSellProfit track the maximum profit after the first and second transactions, initialized to 0.

• Transaction Logic in Loop:

  • Iterates through each stock price:
    • firstBuyCost updates to the minimum of its current value and the current stock price.
    • firstSellProfit calculates the maximum of its current value and the difference between the current stock price and firstBuyCost.
    • secondBuyCost then adjusts to include the net expenditure after the first transaction's profit by finding the minimum of its current value and the difference between the current stock price and firstSellProfit.
    • secondSellProfit finally updates to the maximum of its current value and the difference between the current stock price and secondBuyCost.

• Return Value:

  • The function returns secondSellProfit, which will be the maximum profit achievable with two transactions.

This function efficiently computes the result using a single for loop, ensuring that the solution is optimal for typical input sizes where multiple iterations like dynamic programming would be less efficient. However, ensure that stock array data are integer values and the length is correct to avoid runtime errors.

var calculateMaxProfit = function (stockPrices) {
    let firstTransactionCost = Number.MAX_VALUE,
        secondTransactionCost = Number.MAX_VALUE;
    let firstTransactionProfit = 0,
        secondTransactionProfit = 0;

    for (let currentPrice of stockPrices) {
        firstTransactionCost = Math.min(firstTransactionCost, currentPrice);
        firstTransactionProfit = Math.max(firstTransactionProfit, currentPrice - firstTransactionCost);

        secondTransactionCost = Math.min(secondTransactionCost, currentPrice - firstTransactionProfit);
        secondTransactionProfit = Math.max(secondTransactionProfit, currentPrice - secondTransactionCost);
    }
    return secondTransactionProfit;
};

The JavaScript function named calculateMaxProfit provided is designed to calculate the maximum profit that can be achieved from making at most two transactions on a given list of stock prices. This function implements an optimized solution based on dynamic programming principles. Here's a concise explanation of how the function works:

• Initialize variables to track the cost of the first and second transactions (firstTransactionCost and secondTransactionCost) as well as the profits from these transactions (firstTransactionProfit and secondTransactionProfit). Initial costs are set to Number.MAX_VALUE to ensure that any actual stock price will be lower, starting the tracking of the minimum price so far.

• Iterate through each stock price in the input array stockPrices:

  • Update firstTransactionCost to store the minimum price encountered so far.

  • Calculate firstTransactionProfit as the maximum of the current firstTransactionProfit or the difference between the current price and the firstTransactionCost.

  • Update secondTransactionCost, factoring in the profit from the first transaction. This tracks the effective cost of buying a second stock after gaining from the first stock sale.

  • Calculate secondTransactionProfit as the maximum of the current secondTransactionProfit or the difference between the current price and the secondTransactionCost.

• Return secondTransactionProfit, which represents the highest possible profit from two transactions.

This solution effectively manages to capture the best moments to buy and sell stocks twice by keeping ongoing tabs on how potential profits accrue across transactions, allowing the individual to maximize their financial gain.

class Solution(object):
    def calculate_max_profit(self, daily_prices: List[int]) -> int:
        first_buy_cost, second_buy_cost = float("inf"), float("inf")
        first_sell_profit, second_sell_profit = 0, 0

        for price in daily_prices:
            first_buy_cost = min(first_buy_cost, price)
            first_sell_profit = max(first_sell_profit, price - first_buy_cost)
            second_buy_cost = min(second_buy_cost, price - first_sell_profit)
            second_sell_profit = max(second_sell_profit, price - second_buy_cost)

        return second_sell_profit

This Python solution tackles the problem of finding the maximum profit from two transactions on stock prices, given a list of daily prices. It employs a dynamic approach where four variables are cleverly utilized to keep track of the costs and the profits of two potential transactions throughout the list of daily prices.

Here's a breakdown of the solution code:

• Initialise two variables first_buy_cost and second_buy_cost to infinity. These represent the lowest prices at which the first and second stocks are bought respectively.
• Initialise two other variables first_sell_profit and second_sell_profit to zero. These capture the highest profit from selling the stocks bought at first_buy_cost and second_buy_cost.
• Loop through each price in daily_prices:
  • Update first_buy_cost to the minimum of itself and the current price.
  • Update first_sell_profit to the maximum of itself and the difference between the current price and first_buy_cost.
  • Update second_buy_cost by subtracting first_sell_profit from the current price, making sure it is the minimum seen so far.
  • Calculate second_sell_profit as the maximum value between its current value and the difference between the current stock price and second_buy_cost.
• Return second_sell_profit, which holds the maximum profit achievable with up to two transactions.

The usage of minimal and maximal evaluations at each step ensures that the best buying and selling decisions are made based on the prices seen so far, guaranteeing that the final result is optimized for the highest possible profit.