42.LeetCode121.买卖股票的最佳时机

• 标签： 动态规划 数组
• 难度： 简单

• 题目描述：

• 我的解法

设 [1,n-1] 天内的股票最低价为 v(n-1), 最大利润为 gain(n-1), 则在得知第 n 天的股价 prices[n] 后， 可以求出在 [1,n] 天内的股票最低价 v(n) 和 gain(n) 的推导公式为：
v(n) = min (v(n- 1), prices[n]), gain(n) = max(gain(n-1), prices[i] - v)。

# 我的写法1（分析思路更自然）
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        v = prices[0]
        gain = 0
        for i in range(1, len(prices)):
            if prices[i] > v:
                if prices[i] - v > gain:
                    gain = prices[i] - v
            else:
                v = prices[i]
        return gain
    
#我的写法2（语法更简洁）
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        v = prices[0]
        gain = 0
        for i in range(1, len(prices)):
            v = min(v, prices[i])
            gain = max(gain, prices[i] - v)
        return gain

• 其他解法

赞略。