网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1010. -- 最优规则式

1010: 最优规则式

时间限制: 1 Sec  内存限制: 128 MB
提交: 181  解决: 42
[提交][状态][讨论版]

题目描述

已知一个整形数组arr, 你需要找到满足a<b<c<d的四个数组下标, 使得arr[b]+arr[d]-arr[a]-arr[c]的值最大

输入

第一行输入T,表示测试数据
接下来一行输入n,表示数组长度。( 4 =< n <= 10^5)
接下来输入n个整数,每个数的范围在[0,10^8]

输出

每组数据输出一行,输出满足条件的最大值

样例输入

1
7
2 3 5 8 1 4 9

样例输出

14

提示


对于测试数据,最大的答案为:

arr[3]+arr[6]-arr[0]-arr[4] = 9 + 8 - 2 - 1 = 14

来源

[提交][状态][讨论版]