[LeetCode] 121. Best Time to Buy and Sell Stock

Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Maximum profit =  buy at the lowest price and sell at the highest price.

Time Complexity = O ( N )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minSoFar = 2 ** 31 - 1
        profit = 0
        
        for p in prices:
            profit = max(profit, p - minSoFar)
            minSoFar = min(minSoFar, p)
        
        return profit

A greedy solution :

Time Complexity = O ( N )

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        localmax, globalmax = 0, 0
        
        for i in range(1, len(prices)):
            localmax = max(localmax + prices[i] - prices[i-1], 0)
            globalmax = max(localmax, globalmax)
        
        return globalmax

Use localmax to save the maximum profit can get with consecutive days.

If localmax <  0, set localmax = 0 to restart.

Use globalmax to save the maximum localmax be found.

DP solution:

On each day, we either hold stock or sell stock.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        holdStock = -prices[0]
        notHoldStock = 0
        
        for i in range(1, len(prices)):
            # keep holding stock or buy stock
            # don't accumulate profit, since it can only buy once
            holdStock = max(holdStock, -prices[i])
            
            # keep not holding stock or sell stock
            notHoldStock = max(notHoldStock, holdStock + prices[i])
        
              
        # on the last day, we get the maximum profit when not hold any stock
        return notHoldStock