Untitled
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; } }