problem:

<aside>

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.

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.

</aside>

solution:

<aside>

• buy on the cheapest day and sell on the most expensive day → find pair of elements where left is lowest possible and right is highest possible
• Always buy at the lowest price seen so far
• At each day, check if selling today gives better profit
• Update best profit

single-pass greedy + prefix minimum problem.

• Track the lowest price so far

• At each step, compute:

  profit = current_price - min_price_so_far
  

• Keep the maximum profit

at each p in prices buy carries the minimum of the prefix of p and updates accordingly

</aside>

code:

def maxProfit(prices):
		buy = prices[0]
    profit = 0

    for p in prices:
		    buy = min(buy, p)
        profit = max(profit, p - buy)

    return profit

complexity:

<aside>

1 pass through array → O(n) time

2 variables → O(1) space

</aside>

walkthrough:

<aside>

input: [7,1,5,3,6,4]

buy = 7, profit = 0

for:

output: 5

</aside>