话不多说–看题
- 小埋的最大差值
题目ID：6368必做题100分
最新提交：
Accepted
100 分
历史最高：
Accepted
100 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
小埋最近在思考关于数组的问题，想到了一个在一个长度为
n
n 的数组中，具有关于以下性质的最大差值。
数组
n
n 可以均匀分成若干部分（保证一定分完），每一个部分为
k
k 大小的连续区间 。（k可以取任意符合的值）
从数组的第一个元素开始，将连续的
k
k 个元素相加。
a
1
,
a
2
,
.
.
a
k
a
1
,a
2
,…a
k
相加求和，
a
k
+
1
，
a
k
+
2
,
.
.
,
a
2
k
a
k+1
，a
k+2
,…,a
2k
相加。（相加的格式如该描述）
该数组序列是固定的。
任意两个
k
k 区间可以求差(两个k区间中的k是相等的)，找出其中的绝对值最大值。
小埋感觉条件描述有点多，让自己绕晕了，现在请你帮助小埋解决这个问题。
输入格式
第一行输入一个整数
t
t
(
1
<
t
<
1
0
4
)
(1<=t<=10
4
) 代表的测试样例数。
每组样例的第一行输入一个整数
n
n
(
1
<
n
<
150000
)
(1<=n<=150000) 表示数组的元素个数。
第二行是
n
n 个整数
a
1
,
a
2
,
.
.
.
,
a
n
a
1
,a
2
,…,a
n
(
1
<
a
i
<
1
0
9
)
(1<=a
i
<=10
9
)。
数据保证所有样例
n
n 的总和数量不会超过
150000
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，只有两个元素
1
,
2
1,2,极大差值为
1
1。
测试样例
2
2, 我们分成
6
6 部分，其中最大值是
10
10，最小值是
1
1,最大差值为
9
9
数据范围
None
好，看完题目，爱爆枚的你是否立刻想大展身手？
但是 n 最多的因子->2根号n 复杂度为 O(2根号nn)=300000根号下1.510000；
等于1.210000000；
显然易见，会爆！
那该如何进行计算呢？
聪明的孩子已经想到了—前缀和！
那么 我们把他列出来看看
n+n/2+n/3+n/4+n/5…n/n
化简一下n*(1+1/2+1/3+1/4+…+1/n)
很明显 这是一个调和级度；
复杂度只有 O(n*log(n));
本片题解到此还没有结束
务必重视以下内容
务必重视以下内容
务必重视以下内容
务必重视以下内容
不开 long long见祖宗！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！