How to fix this TLE error?

#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?

You are calculating maxbeforei[N],minbeforei[N] in O(N^2). Hence TLE.

You can calculate that in O(N) as follows:

maxbeforei[0] = delish[0];
minbeforei[0] = delish[0];
loop(i,1,N){
maxbeforei[i] = max(maxendi[i],maxbeforei[i-1]);
minbeforei[i] = min(minendi[i],minbeforei[i-1]);}
  • maxendi[i] represents the maximum sum of subarray ending at i (inclusive), Hence maxbeforei[i] equals to the maximum of maximum subarray ending at i (Which we already have) or the previous maxbeforei[i] (Which is maxbeforei[i-1]).
  • Similarly for Minimum.

You can optimize more by removing unnecessary loops, but still, it should pass anyway.

For additional help, you can visit this, Editorial .