题解 | #买卖股票的最好时机(二)# Py3 + 简单解释

import sys

# 对于每天来说，每天可能有三种可操作状态，可买入，可卖出，和不操作三种选择
# 假设当天可买入状态下,从第一台呢到第i天能收获的最高利润是 buy[i]
# 当天可卖出状态下能收获的最高利润是 sell[i]
# 不操作的话收益和 0~i之间某一天的买入或者卖出一样，无需专门记录
# 因此
# buy[i] = max(sell[i-1] - prices[i], buy[i-1])
# sell[i] = max(buy[i-1] + prices[i], sell[i-1]
# 最后能max(buy[i],sell[i]) 即可

n = int(input())
if n <= 1:
    print(0)
else:
    prices = list(map(int,input().strip().split(' ')))
    sell = [0] * (n+1)
    buy = [0] * (n+1)
    buy[0] = - prices[0] #第一天不可卖出，因此让第一天的卖出值为0
    for i in range(1,n+1):
        buy[i] = max(sell[i-1] - prices[i-1], buy[i-1])
        sell[i] = max(buy[i-1] + prices[i-1], sell[i-1])

    max_profit = max(buy[-1],sell[-1])
    if max_profit <= 0:
        print(0)
    else:
        print(max_profit)