题解 | #数据流中的中位数#

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        dp = [ [0, 0] for _ in range(n) ]
        # dp[i][0]第i天持有股票后的最多现金
        # dp[i][1]第i天持有的最多现金
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        
        for i in range(1, n):
            # 第i天持股票所剩最多现金 = max(第i-1天持股票所剩现金, 第i-1天持现金-买第i天的股票)
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            # 第i天持有最多现金 = max(第i-1天持有的最多现金，第i-1天持有股票的最多现金+第i天卖出股票)
            dp[i][1] = max(dp[i-1][1], dp[i-1][1] + prices[i] - prices[i-1])
        
        return max(dp[n-1][0], dp[n-1][1])