Untitled
plain_text
a month ago
1.6 kB
1
Indexable
Never
package Array_Game; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, res; static long sum; static int[] a = new int[20005]; public static int index(int l, int r, long sum){ if(l >= r) return -1; if(sum%2 == 1) return -1; long s = 0; for(int i = l; i < r; i++){ s += a[i]; if(s == sum/2){ return i; } if(s > sum/2){ return -1; } } return -1; } public static void backTrack(int l, int r, int count, long sum) { // System.out.println(l + " " + r + " " + " " + count); // if (sum % 2 == 1) { // res = Math.max(res, count); // return; // } // if(r - l == 1){ // // return; // } int x = index(l, r, sum); if(x == -1){ res = Math.max(res, count); return; } backTrack(l, x+1, count+1, sum/2); backTrack(x+1, r, count+1, sum/2); } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); a = new int[n]; sum = 0; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); sum += a[i]; } res = 0; if(sum == 0){ res = n-1; }else{ backTrack(0, n, 0, sum); } System.out.println(res); } scanner.close(); } }