[LeetCode] Q121, Q122, Q123

Q121

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        m = prices[0]
        profit = 0
        for p in prices:
            if p >= m:
                if p - m > profit:
                    profit = p - m
            else:
                m = p
        return profit

Q122

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

Q123

# TODO: need to prove this must get the correct answer
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        m1 = prices[0]
        profit1 = 0
        m2 = 100001
        profit2 = 0
        for p in prices:
            m1 = min(m1, p)
            profit1 = max(profit1, p-m1)
            m2 = min(m2, -profit1 + p)
            profit2 = max(profit2, p-m2)
        return profit2