小埋的最大差值
题目描述
小埋最近在思考关于数组的问题，想到了一个在一个长度为 n 的数组中，具有关于以下性质的最大差值。
-
数组 n 可以均匀分成若干部分（保证一定分完），每一个部分为 k 大小的连续区间 。（ k 可以取任意符合的值）
-
从数组的第一个元素开始，将连续的 k 个元素相加。
-
a_1,a_2,..a_k 相加求和， a_{k+1}，a_{k+2},..,a_{2k} 相加。（相加的格式如该描述）
-
该数组序列是固定的。
-
任意两个 k 区间可以求差(两个 k 区间中的 k 是相等的)，找出其中的绝对值最大值。
小埋感觉条件描述有点多，让自己绕晕了，现在请你帮助小埋解决这个问题。
输入格式
第一行输入一个整数 t (1<=t<=104) 代表的测试样例数。
每组样例的第一行输入一个整数 n (1<=n<=150000) 表示数组的元素个数。
第二行是 n 个整数 a_1,a_2,...,a_n (1<=a_i<=10^9) 。
数据保证所有样例 n 的总和数量不会超过 150000 。
输出格式
对于每组测试样例，输出一个整数，表示该数组的最大极差。
样例
Input 1
5
2 1 2
6 10 2 3 6 1 3
4 1000000000 1000000000 1000000000 1000000000
15 60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8 19957 69913 37531 96991 57838 21008 14207 19198
Output 1
1
9
0
189114
112141
样例解释
-
测试样例 1 ，只有两个元素 1,2 ,极大差值为 1 。
-
测试样例 2 , 我们分成 6 部分，其中最大值是 10 ，最小值是 1 ,最大差值为 9 。
数据范围
None
思路
我们以这个样例来思考：
6
10 2 3 6 1 3
众所周知，暴力可以解决一切问题，那么我们就试试看枚举 k 的值。
k=\left\{\begin{matrix} 1 ,那么序列为10,2,3,6,1,3,ans=10-1=9\\ 2,那么序列为10,2|3,6|1,3,ans=12-4=8\\ 3,那么序列为10,2,3|6,1,3,ans=15-10=5\\ 4,无法平均分，舍去\\ 5,无法平均分，舍去\\ 6,无法作差，舍去 \end{matrix}\right.
既然要枚举，我们需要知道， n 最多有多少因子呢？
答： 2\sqrt{n} 个。
那么，时间复杂度就是 O(2\sqrt{n}\space\cdot\space n) 。
n=1.5\space\cdot\space10^5 ，那么 2\sqrt{n}\space\cdot\space n 就等于 1.2\space\cdot\space 10^8 ，这个数据已经很危险了，有可能会
，所以，我们需要一个更好的方法。
我们发现，这是一个求连续区间和的题目，我们自然会想到前缀和。
k=\left\{\begin{matrix}
1 ,执行n次\\
2,执行\cfrac{n}{2}次\\
3,执行\cfrac{n}{3}次\\
4,执行\cfrac{n}{4}次\\
5,执行\cfrac{n}{5}次\\
6,执行\cfrac{n}{6}次\\
.\\
.\\
.\\
\end{matrix}\right.
那么总执行次数就是 n+\cfrac{n}{2}+\cfrac{n}{3}+\cfrac{n}{4}+···+\cfrac{n}{n}=n(1+\cfrac{1}{2}+\cfrac{1}{3}+\cfrac{1}{4}+···+\cfrac{1}{n}) 次。
我们惊喜地发现，这不就是调和级数吗，时间复杂度就降到了 O(n\log n) 。
当然，这是求和，注意开 long\space long 。