Home => ProblemSet => 200.1-57:拆分数组
Problem1953--200.1-57:拆分数组

1953: 200.1-57:拆分数组

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

小V想尝试将一个数组拆分为两个非空的连续数组(一个从前往后,一个从后往前),使得两个数组的元素之和相等。
为了增加趣味性,小V可以任意移动一个元素的位置到想要的位置(也可以不移动如果直接就可以拆分的话)。
请你用程序判断小V是否可以拆分出两个和相等的数组呢。

Input

多组测试数据。
第一行一个正整数T,表示有多少组测试数据
每组测试数据第一行一个整数n (1 <= n <= 100000),表示数组元素。
每组测试数据第二行n个整数表示数组元素,空格分隔,1 <= 每个数 <= 109

Output

T行,每行一个结果表示是否可以拆分,可以拆分输出 YES,无法拆分输出 NO

Sample Input Copy

3
3
1 3 2
5
1 2 3 4 5
5
2 2 3 4 5

Sample Output Copy

YES
NO
YES

HINT

样例解释:
第一个测试数据中,可以将第二个元素3移动到数组末尾或开头(或者将第一个元素移动到末尾,或者将第三个元素移动到数组开始或插入元素1和3之间)。
第二个测试数据中,任何移动都无法拆分数组。
第三个测试数据中,可以将第四个元素4插入第二第三两个元素2和3之间(或者将第三个元素3插入元素4和5之间,或者直接移动到末尾,方法不唯一)

50%的数据,n <= 20;
60%的数据,n <= 100;
100%的数据,1 <= n <= 100000, 1 <= 数组元素 <= 109, n的和不超过100000。

Source/Category