题解 | #买卖股票的最好时机(三)# Python3+解释

import sys

# 卖出之前没法买入，
# 假设第一次卖出是在第i天
# 那么就是寻找 0～i天 和i到n天两段时间内的最大收益
# 因此两个动态规划
# dp1 从 0到 i 表示 到第i天的最大收益
# dp2 从 i到n 表示 i~n天的最大收益

n = int(input())
if n <= 1:
    print(0)
else:
    prices = list(map(int,input().strip().split(' ')))
    dp1 = [0] * n
    dp2 = [0] * n
    pre_min = prices[0]
    for i in range(1,n):
        dp1[i] = max(dp1[i-1],prices[i]-pre_min)
        pre_min = min(prices[i],pre_min)

    pre_high = prices[-1]
    for j in range(n-2,-1,-1):
        dp2[j] = max(dp2[j+1],pre_high - prices[j])
        pre_high = max(pre_high, prices[j])
        
    res = [v1+v2 for v1,v2 in zip(dp1,dp2)]
    max_profit = max(res)
    if max_profit <=0:
        print(0)
    else:
        print(max_profit)