题目要点

这个题目的前置题目是 1054 ，即仅进行一次交易，如何保证利润最大，我们使用了递推来求解。
两次交易，对于任意点i，划分左半边利润最大(pre)和右半边利润最大(post)，然后相加就是两次交易。
思路有点类似于 482 的合唱队形题目。

算法1

(DP) $O(n)$

一次正向 DP + 一次反向 DP

Python 代码

"""
AcWing 1056. 股票买卖 III
"""
N = 100010
pre, post = [0] * N, [0] * N

n = int(input())
data =[int(d) for d in input().split()]

idx = 0
for i in range(n):
    pre[i] = max(pre[i - 1], data[i] - data[idx])
    if data[i] < data[idx]:
        idx = i

idx = n - 1
for i in range(n - 1, -1, -1):
    post[i] = max(post[i + 1], data[idx] - data[i])
    if data[i] > data[idx]:
        idx = i

res = 0
for i in range(n):
    res = max(res, pre[i] + post[i])
print(res)