Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.7 kB
0
Indexable
Never

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class CopyOfArrayGame2 {
	static{
		try {
			System.setIn(new FileInputStream("src/inp.txt"));
//			System.setOut(new PrintStream("src/out.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	static Scanner scanner=new Scanner(System.in);
	
	static class Node{
		long sum;
		int i;
		int n;
		int res;
		Node link;
		Node(long s,int i,int n,int r){
			this.sum=s;
			this.i=i;
			this.n=n;
			this.res=r;
		}
	}
	
	static class Stack{
		Node front;
		int n;
		void push(Node node){
			++n;
			node.link=front;
			front=node;
		}
		void pop(){
			if(front==null)
				return;
			--n;
			front=front.link;
		}
	}
	
	/*DUNG STACK LAM DE QUY, MOI THAM SO HAM DE QUY TUONG UNG VOI 1 STACK
	 * static void run(long sum,int i,int n,int res) ... 
	 * static void run(Stack stack) {
		long sum=stack.front.sum;
		int i=stack.front.i;
		int n=stack.front.n;
		int res=stack.front.res;
		stack.pop();
		
		Res=Math.max(Res,res);
		
		if(i>=n || (sum&1)>0)
			return;
		
		long s1=sum;
		long s2=0;
		
		for(int j=i;j<=n;++j) {
			s1-=a[j];
			s2+=a[j];
			
			if(s1==s2){
				stack.push(new Node(s1,i,j,res+1));
				stack.push(new Node(s2,j+1,n,res+1));
				return;
			}
		}
	}
	 * */
	
	static void exec() {
		int n=Integer.parseInt(scanner.next());
		int[] a=new int[n];
		long Res=0,s=0;
		
		for(int i=0;i<n;++i){
			a[i]=Integer.parseInt(scanner.next());
			s+=a[i];
		}
		
		Stack stack=new Stack();
		stack.push(new Node(s,0,n-1,0));//so diem ban dau =0
		
		while(stack.n>0){
			long sum=stack.front.sum;
			int left=stack.front.i;
			int right=stack.front.n;
			int res=stack.front.res;
			stack.pop();
			
			Res=Math.max(Res,res);//note cai nay phai de tren dieu kien if(left>=right || (sum&1)>0) do tinh ca truong hop tong la so am thi ko chia dc
			
			if(left>=right || (sum&1)>0)
				continue;
			
			long s1=sum;//tong ben phai
			long s2=0;	//tong ben trai
			for(int j=left;j<=right;++j) {
				s1-=a[j];//o phan tu j hien tai thi bo di a[j] o ben phai, de cho vao ben trai
				s2+=a[j];
				
				if(s1==s2){//2 ben bang nhau
					stack.push(new Node(s1,left,j,res+1));//moi lan chia dc tang 1 diem, sau do lai tiep tuc voi ben trai, phai sai khi chia dc
					stack.push(new Node(s2,j+1,right,res+1));
					break;
				}
			}
		}
		
		System.out.println(Res);
	}
	
	public static void main(String[] args) {
		int t=Integer.parseInt(scanner.nextLine());
		
		for(int test=1;test<=t;++test)
			exec();
		
		scanner.close();
	}
}