used n*n dp but gave MLE
code is acc to hint provided:
#include<bits/stdc++.h>
using namespace std;
#define ll long
int f(int *arr,int i,int j,int **dp,ll *ps)
{
if(i>=j)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
int m=0;
for(int p=i;p<j;p++)
{
ll left=ps[p]-ps[i]+arr[i];
ll right=ps[j]-ps[p+1]+arr[p+1];
if(left==right)
{
int a=f(arr,i,p,dp,ps);
int b=f(arr,p+1,j,dp,ps);
int ans=1+max(a,b);
m=max(ans,m);
}
}
dp[i][j]=m;
return m;
}
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++)cin>>arr[i];
ll *ps=new ll[n];
ps[0]=arr[0];
for(int i=1;i<n;i++)
{
ps[i]=arr[i]+ps[i-1];
}
int **dp=new int*[n];
for(int i=0;i<n;i++)
{
dp[i]=new int[n];
for(int j=0;j<n;j++)
{
dp[i][j]=-1;
}
}
cout<<f(arr,0,n-1,dp,ps)<<endl;
}
return 0;
}