CF1868E.Min-Sum-Max
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
The first line of input contains a single integer t ( 1≤t≤50 ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤300 ) — the length of the array a .
The second line of each test case contains n integers a1,a2,…,an ( −109≤ai≤109 ) — the elements of the array a .
It is guaranteed that the sum of n over all test cases does not exceed 1000 .
输入格式
For each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array a .
输出格式
In the first test case, Daniel can divide the array into [−1] and [5,4] , and s=[−1,9] . It can be shown that for any i=j , the condition in the statement is already satisfied, and for i=1,j=2 , we have min(−1,9)≤(−1)+9≤max(−1,9) .
In the second test case, if Daniel divides the array into [2023] and [2043] , then for i=1,j=2 we have 2023+2043>max(2023,2043) , so the maximum number of subsegments is 1 .
In the third test case, the optimal way to divide the array is [1,4,7],[−1],[5,−4] .
In the fourth test case, the optimal to divide the array way is [−4,0,3,−18],[10] .
In the fifth test case, Daniel can only get one subsegment.
输入输出样例
输入#1
8 3 -1 5 4 2 2023 2043 6 1 4 7 -1 5 -4 5 -4 0 3 -18 10 1 998244853 10 -4 2 5 -10 4 8 2 9 -15 7 7 -7 3 8 -9 -2 2 4 4 -5 5 -2 -5
输出#1
2 1 3 2 1 6 5 3
说明/提示
In the first test case, Daniel can divide the array into [−1] and [5,4] , and s=[−1,9] . It can be shown that for any i=j , the condition in the statement is already satisfied, and for i=1,j=2 , we have min(−1,9)≤(−1)+9≤max(−1,9) .
In the second test case, if Daniel divides the array into [2023] and [2043] , then for i=1,j=2 we have 2023+2043>max(2023,2043) , so the maximum number of subsegments is 1 .
In the third test case, the optimal way to divide the array is [1,4,7],[−1],[5,−4] .
In the fourth test case, the optimal to divide the array way is [−4,0,3,−18],[10] .
In the fifth test case, Daniel can only get one subsegment.