## Table of contents

## Open Table of contents

## Problem

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 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.
```

**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`

## Explanation/Approach

The goal is to find the maximum difference between two numbers in the array where the larger number comes after the smaller one. This represents the maximum profit.

**One-pass Approach:**Iterate through the array, updating the minimum price so far and the maximum profit at each step.

## Solution: One-pass Approach

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price = float('inf') # Initialize min price to infinity
max_profit = 0 # Initialize max profit to 0
# Iterate over the prices
for price in prices:
# Update the min price if the current price is lower
min_price = min(min_price, price)
# Update the max profit if the current profit is higher
max_profit = max(max_profit, price - min_price)
return max_profit
```

**Time and Memory Complexity**

The time complexity is O(n), where n is the number of days, as we only iterate through the list once. The space complexity is O(1) since we only use two variables regardless of the input size.

**Explanation**

The algorithm maintains two variables: `min_price`

, which represents the lowest price seen so far, and `max_profit`

, the highest profit that can be made by selling at the current price. For each price in the list, it checks if the current price is lower than the `min_price`

and updates it. Then, it calculates the profit that could be made by selling at the current price and updates `max_profit`

if this profit is higher than the current `max_profit`

. The final value of `max_profit`

is the answer.