题解 | #买卖股票的最好时机(一)#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        """
        step1: dp[i][0] 表示第i天不持股到该天位置的最大收益，dp[i][1] 表示第i天持股，到该天为止的最大收益
        step2: 初始状态，第一天不持股，总收益为0，dp[0][0] = 0； 第一天持股，总收益为买股票花费， dp[0][1] = -prices[0]
        step3: 状态转移，对于之后的每天，当天不持股，总收益和前一天相同；当天卖掉，dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
        step4: 当天持股，若干天买，当天没卖，收益与前一天相同；当天买入，此时收益为负股价，选最大：dp[i][1] = max(dp[i-1][1],-prices[i])

        """
        n = len(prices)

        dp = [[0] * 2 for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]

        # 遍历后，状态转移
        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1],-prices[i])
        return dp[n-1][0]