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`

.

Examples:

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

```
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
```

## Sliding window / two pointer solution

- Initialize a left pointer
`left`

on day 1, and a right pointer`right`

on day 2 - Find the current profit (buy on
`left`

, sell on`right`

)- if
`right`

is less than`left`

- update
`left`

to be`right`

, and - update
`right`

to be the next day

- update
- if
`left`

is less than`right`

(it's a profit)- if the profit (
`right - left`

) is more than`max_profit`

, set it to`max_profit`

- only update
`right`

(because we are buying low and selling high) to the next day

- if the profit (
- repeat step

- if
- Return
`max_profit`

The memory is O(1) because only pointers are used. The time is O(n).

## Python

```
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
left = 0
right = 1
# while we haven't reached the end
while right < len(prices):
left_value = prices[left]
right_value = prices[right]
# profitable?
if left_value < right_value:
profit = right_value - left_value
max_profit = max(max_profit, profit)
else:
left = right
right += 1
return max_profit
```