fork download 
  1. import java.util.*;
  2. public class Main {
  3. 	//static long dp[][];
  4. 	static long pre[];
  5.     public static void main(String args[]) {
  6. Scanner sc=new Scanner(System.in);
  7. int t=sc.nextInt();
  8. while(t-->0){
  9. 	int n=sc.nextInt();
  10. 	int arr[]=new int[n];
  11. 	for(int i=0;i<n;i++)
  12. 	arr[i]=sc.nextInt();
  13.  
  14.  
  15.     pre=new long[n+1];
  16.    pre[0]=0;
  17.    //pre[1]=arr[1];
  18.  
  19.    for(int i=1;i<=n;i++)
  20.    pre[i]=pre[i-1]+arr[i-1];
  21. 	//dp=new long[n][n];
  22. 	// for(int i=0;i<n;i++)
  23. 	// Arrays.fill(dp[i],(long)-1);
  24. System.out.println(f(arr,0,n-1));
  25. } 
  26.     }
  27. 	static long f(int arr[],int i,int j){
  28.            if(i>=j)
  29. 		   return 0;
  30. 		   if(i+1==j){
  31. 			   if(arr[i]==arr[j])
  32.                return 1;
  33. 			   else
  34. 			   return 0;
  35. 		   }
  36. 	long result=0;
  37. 		   for(int k=i;k<j;k++){
  38. 			   long ans=0;
  39. 			   if(pre[k+1]-pre[i]==pre[j+1]-pre[k+1]){
  40. 			    ans= 1+(long)Math.max((long)f(arr,i,k),(long)f(arr,k+1,j));
  41. 			   result=Math.max(result,ans);
  42. 			   break;
  43. 			   }
  44. 		   }
  45. 		   //dp[i][j]=result;
  46. 		   return result;
  47. 	}
  48.  
  49. }
Success #stdin #stdout 0.1s 35356KB
comments (?)
stdin 
3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1
stdout 
0
2
3
https://ideone.com/vjNYS1
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!