Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
2
Indexable
Never
package ArrayGame;

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

/**
 * Solution
 */
public class Solution {
    static int n,sum,max;
    static int[] a;

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("input.txt"));
        System.setOut(new PrintStream("output.txt"));
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 0; t < tc; t++) {
            n = sc.nextInt();
            a = new int[n];
            sum = 0;
            max = 0;
            boolean fullZero = true;
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
                sum += a[i];
                if(a[i]!=0) fullZero = false;
            }
            if(fullZero){
                System.out.println(n-1);
            }
            else{
                Try(0, n-1, 0);
                System.out.println(max);
            }
        }
    }
    static void Try(int l, int r, int p){
        max = Math.max(max, p);
        int x = balance(l, r);
        if(x==-1) return;
        Try(l, x, p+1);
        Try(x+1, r, p+1);
    }
    static int balance(int l,int r){
        if(l>=r) return -1;
        int tong = 0;
        for (int i = l; i <= r; i++) {
            tong += a[i];
        }
        if(tong%2==1) return -1;
        int tmp = 0;
        for(int i=l;i<=r;i++){
            tmp += a[i];
            if(tmp == tong/2){
                return i;
            }
            else if(tmp>tong/2) break;
        }
        return -1;
    }
}