编程题目，哪位大神教我做，谢谢！

Problem Description
长度为 n 的序列，把它划分成两段非空的子序列，定义权值为：两段子序列的最大值的差的绝对值。求可能的最大的权值。
数据范围：
2 <= n <= 10^6 ， 0 < 序列内的数 <= 10^6 。
Input
第一行输入一个 T，表示有　T　组数据。
接下来有 T 组数据，每组数据的第一行输入一个数 n ，第二行输入 n 个数。
Output
每组数据输出可能的最大的权值。
Sample Input
1
3
1 2 3
Sample Output
2

 #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
int a[N], pre[N], sum[N];
int main() {
    int T;
    cin>> T;
    while(T--) {
        int n;
        cin >> n;
        memset(sum, 0, sizeof(sum));
        memset(pre, 0, sizeof(pre));
        for(int i = 1; i <= n; i ++) cin >> a[i];
        for(int i = 1; i <= n; i ++) {
            sum[i] = max(sum[i-1], a[i]);
        }
        for(int i = n; i > 0; i --) {
            pre[i] = max(pre[i+1], a[i]);
        }
        int MAX = -1;
        for(int i = 2; i <= n; i ++){
            MAX = max(MAX, abs(pre[i]-sum[i-1]));
        }
        printf("%d\n",MAX);
    }
    return 0;
}

感觉直接求这个序列中的最大值减去最小值的绝对值就可以了

这道题很容易想到枚举中间点，然后找两段序列的最大值，但是这样做的时间复杂度为O(n^2)，规定时限1s可能无法完成，首先我们枚举i，i在枚举时，可以顺便更新最大值，从而在O(n)时间找出序列a[1, i-1]的最大值，而至于序列a[i, n]的最大值，我们可以设一个p[i]表示序列a[i, n]的最大值，倒序枚举i，就可以在O(n)时间处理a[i,n]的最大值。然后就可以O(n)枚举，O(1)求权值，也就不会超时了。