设总和为 S=∑i=1nai。
需要判断是否存在“非整段”的连续子段,其和 ≥S。
关键结论:所有“非整段”的连续子段的最大子段和,等于
某片场需要给参演人员采购盒饭,负责后勤的小周来到食堂,食堂里一共有 n 种不同的盒饭,种类标记为 1,2,3,...,n ,每种盒饭都有一个美味度 ai 。ai 越大,表示盒饭越好吃,由于有些盒饭味道可能很奇怪,于是 ai 有可能小于等于 0 。
小周不了解演员们的口味偏好,于是每种盒饭都买了一份。回片场的路上小周在想:能不能找到这样一对 l,r 满足 1≤l≤r≤n ,且不满足 [l,r]=[1,n] (即全选),使得将 [l,r] 这个种类内的盒饭各要一份,其美味度之和大于等于每一种会饭都买一份的美味度之和?
第一行一个正整数 T ,表示有 T 组数据。
对于每一组数据,第一行一个正整数 n ; 第二行 n 个数 a1,a2,...,an 。
3≤n≤5∗104,−100≤ai≤100,1≤T≤5
对于每一组数型,如果找得到这样的 l,r ,输出 Yes ; 否则,输出 No 。
输入
2
4
1 2 3 4
3
-5 5 -5
输出
No
Yes
说明
第一组数据,无论 l,r 如何选择都比全选的美味度之和要小;
第二组数据,可以选择 [l,r]=[1,1] ,美味度之和为 −5 ,等于全部选择的美味度之和。
当然也可以选择 [l,r]=[1,2] ,美味度之和为 0 ,大于全部选择的美味度之和。