Given an array, prices, where prices[i] represent the price of a stock on the i-th day, maximize profit by selecting a single day to buy the stock and a different day in the future to sell it.

Return the maximum profit that can be achieved from this transaction. If no profit can be made, return 0.

Constraints:

• We can’t sell before buying a stock, that is, the array index at which stock is bought will always be less than the index at which the stock is sold.

• $1$ $\leq$ prices.length $\leq$ $10 ^ 3$

• $0$ $\leq$ prices[i] $\leq$ $10^5$

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

A naive approach to solving this problem is to evaluate all possible combinations of buying and selling the stock to determine the maximum achievable profit. This can be implemented using nested loop:

1. The outer loop selects a day to buy the stock by iterating through the prices array.

2. The inner loop starts from the day after the chosen buying day and iterates through the remaining days to select the selling day.

For each combination of buy and sell days, the profit is calculated using the formula: profit = prices[sell] - prices[buy]

Update the maximum profit if the current profit exceeds the previously recorded maximum. As the algorithm evaluates all possible pairs of buy and sell days, the time complexity is $O(n^2)$, where n is the length of the input array. This approach requires only a constant amount of additional space, so the space complexity is $O(1)$. 

To find the maximum profit efficiently, we use a greedy algorithm that relies on two pointers:

• Buy pointer: It starts on the first day and updates whenever a lower price is encountered, ensuring it always tracks the lowest price so far and represents the best day to buy.

• Sell pointer: Iterates through the price list from the second day onward to identify potential selling days and calculate profits relative to the current buy pointer.

At each step, the algorithm evaluates the profit achieved by selling on the current day (indicated by the sell pointer) relative to the day marked by the buy pointer. If selling on the current day generates a higher profit than previously recorded, the maximum profit is updated. If the price on the sell day is lower than or equal to the buy day’s price, the buy pointer is adjusted to match the sell day, ensuring a new, more optimal buying point is selected.

The steps of the algorithm are as follows:

1. Initialize the variables below:

   1. buy = 0: Tracks the index of the day to buy the stock (starts at day 0).

   2. sell = 1: Tracks the index of the day to sell the stock (starts on day 1, i.e., the day after buying).

   3. maxProfit = 0: This will store the maximum profit encountered.

2. Traverse the prices array using the sell pointer,  ensuring it stays within the array’s bounds. For each pair of buy and sell:

   1. Compute the current profit as: profit = prices[sell] - prices[buy].

   2. If the price on the sell day (prices[sell]) is greater than the price on the buy day (prices[buy]), update maxProfit with the greater value between the current profit and the existing maxProfit.

   3. If the price on the sell day (prices[sell]) is less than or equal to the price on the buy day (prices[buy]), update the buy pointer to the current sell day to select a new, more optimal buying day.

   4. Increment the sell pointer to explore the next possible selling day.

3. After the end of the iterations, maxProfit will hold the maximum achievable profit and return maxProfit.

Let’s look at the following illustration to get a better understanding of the solution: