#include<bits/stdc++.h>
using namespace std;
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=b-1;i>=a;i–)
#define INF 1000000000
#define ll long long int
main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int test;cin>>test;
while(test--)
{
int N;cin>>N;
ll zero=0;
ll delish[N];loop(i,0,N){cin>>delish[i];}
ll maxstarti[N];maxstarti[N-1]=delish[N-1];loopr(i,0,N-1){maxstarti[i]=max(zero,maxstarti[i+1])+delish[i];};
// {cout<<maxstarti[i]<<" ";}cout<<endl;
ll minstarti[N];minstarti[N-1]=delish[N-1];loopr(i,0,N-1){minstarti[i]=min(zero,minstarti[i+1])+delish[i];};
// {cout<<minstarti[i]<<" ";}cout<<endl;
ll maxendi[N];maxendi[0]=delish[0];loop(i,1,N){maxendi[i]=max(zero,maxendi[i-1])+delish[i];};
// {cout<<maxendi[i]<<" ";}cout<<endl;
ll minendi[N];minendi[0]=delish[0];loop(i,1,N){minendi[i]=min(zero,minendi[i-1])+delish[i];};
// {cout<<minendi[i]<<" ";}cout<<endl;
ll maxbeforei[N];loop(i,0,N){maxbeforei[i]=-INF;loop(j,0,i+1){maxbeforei[i]=max(maxbeforei[i],maxendi[j]);}};
// {cout<<maxbeforei[i]<<" ";}cout<<endl;
ll minbeforei[N];loop(i,0,N){minbeforei[i]=INF;loop(j,0,i+1){minbeforei[i]=min(minbeforei[i],minendi[j]);}};
// {cout<<minbeforei[i]<<" ";}cout<<endl;
ll answer1=-INF;loop(i,0,N-1){answer1=max(answer1,maxstarti[i+1]-minbeforei[i]);}
ll answer2=-INF;loop(i,0,N-1){answer2=max(answer2,-minstarti[i+1]+maxbeforei[i]);}
cout<<max(answer1,answer2)<<endl;
}
}
This is a correct solution for DELISH Problem - CodeChef.
It is getting TLE. Any suggestions to improve?