class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        """
        2D DP: each row cell stores [min_price_so_far, max_profit_so_far]
        """
        dp = [[0, 0] for _ in range(len(prices))]
        dp[0][0] = prices[0]

        for i in range(1, len(prices)):
            dp[i][0] = min(dp[i-1][0], prices[i])
            dp[i][1] = max(dp[i-1][1], prices[i] - dp[i][0])

        return dp[len(prices)-1][1]