信息学奥赛一本通 1302：股票买卖（evd）
===
> https://www.cnblogs.com/xwf2005/p/17877940.html
先算出一個 0~i的最小值表格 z
再算當下位置i-z[i]跟f1前一項的最大值 f1
再算所有的最大值-z[i]跟f2後一項的最大值 f2
7
5 14 -2 4 9 3 17
z : 5 5 -2 -2 -2 -2
f1: 0 9 9 9 11 11 19
f2: 19 19 19 14 14 14 0
f1 + f2總和最大值等於答案
---

t = int(input())
while t > 0:
    n = int(input())
    z = [int(i) for i in input().split()] 
    z2 = [0] * (n+1)
    z3 = [0] * (n)
    mi = 9999999999
    for i in range(n):
        mi = min(mi,z[i])
        z3[i] = max(z3[i-1],z[i]-mi)
    maa = -2
    for i in range(n-1,-1,-1):
        maa = max(maa,z[i])
        z2[i] = max(z2[i+1],maa-z[i])
    ma = -1
    for i in range(n):
        ma = max(ma,z2[i] + z3[i])
    print(ma)
    t -= 1