题目内容

小塔有一个长度为$n$的数组，他想要选择一个下标$i(1≤i<n)$，随后，将$a_i$及其左边元素全部染红，$a_i$右边的元素全部染蓝，使得红色元素的极差和蓝色元素的极差†的差的绝对值最小，请你直接输出这个值。

†:极差 是指数组中最大值和最小值的差。

思路:简单动态规划:前缀最值

一个显然的思路是枚举染色的断点，然后分别计算前缀和后缀的极差，相减取绝对值。这些答案里取最小即可。

由于n 比较大，我们需要提前算出前缀每个位置的极差，以及后缀每个位置的极差。

f1[i] 表示前i 个位置的极差，f2[i] 表示后i 个位置的极差。

f1[i] = max(max[i-1], a[i]) - min(min[i-1], a[i])

注意这里的max[i-1]和max[i-1]可以用一个变量维护，不需要开辟数组去存储。