Leetcode 121. 买卖股票的最佳时机

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解法

对于价格列表中的每个元素，可以执行的操作有三种：

• 买入
• 卖出
• 不作操作

从是否持有股票来说分为两种状态：

• 持有股票
• 未持有股票

以变量 j 表示持有股票的状态，不妨以 0 表示未持有股票，1 表示持有。

初始利润为 0，不妨以

f(i,j)

表示第 i 个元素在状态 j 时的利润，则题目所求的目标即为

f(n-1,0)

的值。

j 的值只有 0 和 1。当状态为 0 时，有

f(i,0)=max[f(i-1,0),f(i-1,1)+prices[i]]

，其中

f(i-1,0)

表示前一天状态也为 0，今天不作操作，不执行买入，所以利润不变；

f(i-1,1)+prices[i]

表示前一天持有股票，今天执行卖出操作，利润为前一天的利润加今天的卖出价格。所以

f(i,0)

取两者中的较大值。

同理，当状态为 1 时，有

f(i,1)=max[f(i-1,1), 0-prices[i]]

，其中

f(i-1,1)

表示前一天状态也为 1，今天不作操作，不执行卖出，所以利润不变；

0-prices[i]

表示前一天未持有股票，即利润为 0，今天执行买入，利润为初始利润减今天的买入价格。所以

f(i,1)

取两者中的较大值。

观察递推关系式：

f(i,0)=max[f(i-1,0),f(i-1,1)+prices[i]]

f(i,1)=max[f(i-1,1), 0-prices[i]]

可以发现

f(i,0)

依赖

f(i-1,0)

和

f(i-1,1)

，

f(i,1)

依赖

f(i-1,1)

，所以不妨以

i0、i1

分别表示

f(i,0)、f(i,1)

，则有

i0=max[i0,i1+prices[i]], i1=max[i1,0-prices[i]]

。

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