Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
774 B
1
Indexable
Never
#include<iostream>
using namespace std;
int arr[1000000];
int N;
int count;
int ans;

void  chia(int start, int end, long long sum, int score){
	if (ans < score) ans = score;

	if (sum %2 == 1) return;
	long long tmpSum =0;
	for (int i = start; i<end; i++) {
		tmpSum += arr[i];
		if (tmpSum > sum/2) return;
		else if(tmpSum ==sum/2) {
			chia(start, i+1, tmpSum,score+1);
			chia(i+1,end,tmpSum,score+1);
			break;
		}

	}
}
int main()
{
	freopen("text.txt","r",stdin);
	int t;
	cin>>t;
	for(int tc=1;tc<=t;tc++){
		cin>>N;
		long long sum=0;
		for(int i=0; i<N;i++){
			cin>>arr[i];
			sum+=arr[i];
		}
		ans=0;
		int  score=0;
		if(sum==0) {
			ans=N-1;
		}
		else chia(0,N,sum,score);
		cout<<ans<<endl;

	}
	return 0;
}