Solution: Best Time to Buy and Sell Stock
Problem Statement
You are given an array prices
where prices[i]
is the price of a given stock on the i^{th} 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.
Examples

 Input: [3, 2, 6, 5, 0, 3]
 Expected Output: 4
 Justification: Buy the stock on day 2 (price = 2) and sell it on day 3 (price = 6). Profit = 6  2 = 4.

 Input: [8, 6, 5, 2, 1]
 Expected Output: 0
 Justification: Prices are continuously dropping, so no profit can be made.

 Input: [1, 2]
 Expected Output: 1
 Justification: Buy on day 1 (price = 1) and sell on day 2 (price = 2). Profit = 2  1 = 1.
Solution
 Understanding the Problem:
 The problem is to find the maximum difference between two numbers in an array, where the larger number comes after the smaller number.
 Approach:
 Initialize two variables,
minPrice
andmaxProfit
.  Iterate through the list of prices.
 For each price, calculate the profit that can be made by selling at that price (current price 
minPrice
).  Update
maxProfit
if the calculated profit is greater than the currentmaxProfit
.  Update
minPrice
if the current price is less thanminPrice
.
 For each price, calculate the profit that can be made by selling at that price (current price 
 Initialize two variables,
 Why This Works:
 This approach works by keeping track of the minimum price encountered so far and the maximum profit that can be made with that minimum price.
 By continuously updating these two variables, the algorithm ensures that the maximum profit is always calculated relative to the lowest price encountered so far.
Algorithm Walkthrough
Consider the input [3, 2, 6, 5, 0, 3]
:
 Initialize
minPrice
asinfinity
andmaxProfit
as0
.  Iterate through the list:
 Day 1: price is
3
minPrice
is updated to3
. Profit =
3  3 = 0
.maxProfit
remains0
.
 Day 2: price is
2
minPrice
is updated to2
. Profit =
2  2 = 0
.maxProfit
remains0
.
 Day 3: price is
6
minPrice
remains2
. Profit =
6  2 = 4
.maxProfit
is updated to4
.
 Day 4: price is
5
minPrice
remains2
. Profit =
5  2 = 3
.maxProfit
remains4
.
 Day 5: price is
0
minPrice
is updated to0
. Profit =
0  0 = 0
.maxProfit
remains4
.
 Day 6: price is
3
minPrice
remains0
. Profit =
3  0 = 3
.maxProfit
remains4
.
 Day 1: price is
 The final
maxProfit
is4
.
Code
Python3
Python3
. . .
You must run your code first
Complexity Analysis
 Time Complexity: O(n), where n is the number of days. This is because the algorithm iterates through the list of prices once, performing constanttime operations for each price.
 Space Complexity: O(1), as it uses a constant amount of extra space (two variables to keep track of
minPrice
andmaxProfit
).