LeetCode: 121. Best Time to Buy and Sell Stock

The Problem

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

You want 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.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

The Solution

We opted for a simple approach using a for loop

int maxProfit(vector<int>& prices) {
	int profit = 0, minElement = prices.front();

	for(int i = 1; i < prices.size(); ++i) {
		minElement = min(minElement, prices[i]);
		profit = max(profit, prices[i] - minElement);
	}
	return profit;
}

Here's how it works:

1. int maxProfit = 0, minElement = prices.front();: This line initializes two variables, maxProfit and minElement. maxProfit will store the maximum profit obtained, initialized to 0. minElement is initialized with the first element of the prices vector.
2. for(int i = 1; i < prices.size(); ++i) {: This line starts a loop that iterates through the prices vector, starting from the second element (index 1), since we already initialized minElement with the first element.
3. minElement = min(minElement, prices[i]);: This line updates minElement to be the minimum value between the current minElement and the i-th element of the prices vector. This effectively finds the minimum price seen so far.
4. maxProfit = max(maxProfit, prices[i] - minElement);: This line updates maxProfit to be the maximum value between the current maxProfit and the difference between the i-th element of prices and minElement. This effectively calculates the maximum profit that can be obtained if we sell the stock at the i-th day after buying it at the lowest price seen so far.
5. return maxProfit;: Finally, the function returns maxProfit, which represents the maximum profit that can be achieved from buying and selling the stock.