121. Best Time to Buy and Sell Stock

Description:

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.

'''
[1] brute force - Time Limit Exceeded)

code::
def maxProfit(self, prices: List[int]) -> int:
    max_profit=0
    for i in range(len(prices)-1):
        for j in range(i+1,len(prices)):
            if prices[j]>prices[i]:
                max_profit=max(max_profit,prices[j]-prices[i])
    return max_profit

-T/C: O(n^2)
-S/C: O(1)
'''

'''
[2] keeping min price)

idea::
while keeping min_price, find max_profit(== cur_price-min_price) from left to right

code::
def maxProfit(self, prices: List[int]) -> int:
    max_profit=0
    min_price=prices[0]

    for price in prices:
        min_price=min(min_price,price)
        max_profit=max(max_profit,price-min_price)
    return max_profit
    
-T/C: O(n)
-S/C: O(1)
'''

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit=0
        min_price=prices[0]
        
        for price in prices:
            min_price=min(min_price,price)
            max_profit=max(max_profit,price-min_price)
        return max_profit