Best Time to Buy and Sell Stocks

One of the most common problems in stock trading is finding the best time to buy and sell a stock to maximize profits. In this blog post, we will explore an efficient algorithm to solve this problem.

Problem Statement

You are given an array of stock prices, where prices[i] represents the price of a given stock on the ith day. Your task is to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. If you cannot achieve any profit, you should return 0.

Approach

To solve this problem, we can use a simple and intuitive approach. We iterate over the array of stock prices while keeping track of the minimum price we have seen so far. For each price, we calculate the potential profit we can make by selling at that price, and update the maximum profit if necessary.

Here's the step-by-step algorithm:

1. Initialize the minimum price as positive infinity and the maximum profit as 0.

2. Iterate over the array of prices from left to right.

3. For each price, update the minimum price if the current price is lower.

4. Calculate the potential profit by subtracting the minimum price from the current price.

5. Update the maximum profit if the potential profit is greater.

6. After iterating over all prices, return the maximum profit.

Let's implement the code for this algorithm.

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)

    return max_profit

C++ Implementation

int maxProfit(vector<int> &prices)
{
    int minPrice = INT_MAX;
    int maxProfit = 0;

    for (int i = 0; i < prices.size(); i++)
    {
        if (prices[i] < minPrice)
        {
            minPrice = prices[i];
        }
        else if (prices[i] - minPrice > maxProfit)
        {
            maxProfit = prices[i] - minPrice;
        }
    }

    return maxProfit;
}

Example

Let's consider the first example from the problem statement: prices = [7, 1, 5, 3, 6, 4].

Initially, the minimum price is set to positive infinity, and the maximum profit is 0.

1. For the first price, 7, the minimum price is updated to 7 (since it is the first price encountered).

2. For the second price, 1, the minimum price is updated to 1 (since it is lower than the previous minimum price).

3. For the third price, 5, the maximum profit is updated to 4 (5 - 1).

4. For the fourth price, 3, the minimum price remains at 1 (since 3 > 1).

5. For the fifth price, 6, the maximum profit is updated to 5 (6 - 1).

6. For the sixth price, 4, the minimum price remains at 1 (since 4 > 1).

The final maximum profit is 5, which is the correct output.

Complexity Analysis

The time complexity of this algorithm is O(n), where n is the length of the input array prices. This is because we iterate over the array once. The space complexity is O(1) since we only use a constant amount of extra space.

Conclusion

The "Best Time to Buy and Sell Stock" problem can be efficiently solved using a simple algorithm that iterates over the array while keeping track of the minimum price and updating the maximum profit accordingly. This approach allows us to find the best time to buy and sell a stock to maximize our profits.