Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
#include <iostream>
using namespace std;


long long arr[20001];

long long sum(int i , int j) // tinh tong tu i den j
{
	long long sm = 0;
	for(int k = i; k <= j; k++)
	{
		sm = sm + arr[k];
	}
	return sm;
}



void devide(int cnt, int xbgin, int xend, int &max)
{
	long long N1 = sum(xbgin, xend);
	long long sm = 0;
	int index = -1;

	if(max <cnt)
	{
		max = cnt;
	}

	if(xbgin >= xend)
	{
		return;
	}
	// tim vi tri chinh giua cua phan tu
	
	for(int i = xbgin; i <= xend; i++)
	{
		sm = sm + arr[i];
		if(sm == N1 / 2 && sm != 0)
		{
			cnt++;
			index = i;
			break;
		}
	}
	if(index != -1)
	{
	    for(int i = 0; i <= 1; i++)
	    {
		    if(i == 0)
		    {
			     //chon bo phan thu 1
			     devide(cnt, index + 1, xend, max);
		    }
		    else
		    {
			     //lay phan thu nhat
			     devide(cnt, xbgin, index, max);
		     }
	    }
	}
	else
		return;

}

int main()
{
	freopen("input.txt", "r", stdin);
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		int N;
		cin >> N;
		for(int i = 0; i < N; i++)
		{
			cin >> arr[i];
		}
		int max = 0;
	    devide(0, 0,N - 1, max);
		if(sum(0, N -1) == 0)
		{
			max = N -1;
		}
		cout<<max<<endl;
	}
}