题目描述
给定一个数组，它的第 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，不妨以 表示第 i 个元素在状态 j 时的利润，则题目所求的目标即为
的值。
j 的值只有 0 和 1。当状态为 0 时，有 ，其中
表示前一天状态也为 0，今天不作操作，不执行买入，所以利润不变；
表示前一天持有股票，今天执行卖出操作，利润为前一天的利润加今天的卖出价格。所以
取两者中的较大值。
同理，当状态为 1 时，有 ，其中
表示前一天状态也为 1，今天不作操作，不执行卖出，所以利润不变；
表示前一天未持有股票，即利润为 0，今天执行买入，利润为初始利润减今天的买入价格。所以
取两者中的较大值。
观察递推关系式：
可以发现 依赖
和
，
依赖
，所以不妨以
分别表示
，则有
。
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
