Best Time to Buy and Sell Stock

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

SOLUTION:

# class Solution:
#     def maxProfit(self, prices: List[int]) -> int:
#         valIndex = {}
#         maxProfit = 0
#         for i, price in enumerate(prices):
#             if price not in valIndex:
#                 valIndex[price] = [i, i]
#             else:
#                 valIndex[price][1] = i
#         newprices = sorted(valIndex.keys())
#         n = len(newprices)
#         for j in range(n - 1, -1, -1):
#             end = newprices[j]
#             if end - newprices[0] <= maxProfit:
#                 break
#             for i in range(j):
#                 curr = end - newprices[i]
#                 if curr <= maxProfit:
#                     break
#                 if valIndex[end][1] > valIndex[newprices[i]][0]:
#                     maxProfit = max(maxProfit, curr) 
#         return maxProfit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        minSoFar = prices[0]
        maxDiffSoFar = 0
        for i in range(1, n):
            minSoFar = min(minSoFar, prices[i])
            maxDiffSoFar = max(maxDiffSoFar, prices[i] - minSoFar)
        return maxDiffSoFar