Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
963 B
2
Indexable
Never
Array Game


Có 1 trò chơi với dãy gồm N số như sau:
Mỗi bước đi bạn phải chia mảng thành 2 phần không rỗng sao cho tổng các phần tử bên trái bằng tổng phần tử bên phải. Nếu chia được bạn sẽ được 1 điểm, nếu không chia được trò chơi kết thúc.
Sau mỗi lần chia thành công, bạn phải bỏ 1 trong 2 phần đã chia và tiếp tục trò chơi với phần còn lại.
Cho 1 dãy, hỏi số điểm nhiều nhất mà bạn có thể thu được là bao nhiêu?
Input
Dòng đầu tiên là số lượng test case T (T <= 20).
Dòng đầu tiên của mỗi test case là N (N <= 20,000) là số lượng phần tử của dãy. Dòng tiếp theo là N phần tử của dãy đó.
 
Output
Mỗi test case in ra số điểm nhiều nhất mà có thể thu được
 
Sample
Input
3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1
Output
0
2
3



Code: