#include
#include
using namespace std;
int modified_kadens_algorithm(int a[],int array_size)
{
int current_sum=0,max=INT_MIN,max_index,count=2,max_starting_index=array_size;
while(count>0)
{
for(int i=0;i<array_size;i++)
{
//cout<<"Current_sum="<<current_sum<<" max="
<<max<<endl;
if(current_sum==0)
{
max_index=i;
}
current_sum=current_sum+a[i];
if(i<max_starting_index)
{
if(max<current_sum)
{
max=current_sum;
}
if(current_sum<0)
{
current_sum=0;
}
}
}
max_starting_index=max_index;
count--;
}
return max;
}
int main() {
int array_size,a[5000],positive_Number,test_cases;
cin>>test_cases;
while(test_cases>0)
{
positive_Number=1;
cin>>array_size;
for(int i=0;i<array_size;i++)
{
cin>>a[i];
}
for(int i=0;i<array_size;i++)
{
if(a[i]<0)
{
positive_Number=0;
}
}
int
max=modified_kadens_algorithm(a,array_size);
cout<<max<<endl;
test_cases--;
}
}