Rainwater harvesting problem

#1

// this is my code out of 9 my 3 cases were not working and it is written that error TLE
//please tell what is the error and also tell what is TLE error and why it is showing an error
//this is my code
#include
using namespace std;
int main()
{
int n,a[1000000],k,i,j,s=0, left_max[1000000],right_max[1000000];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
right_max[i]=a[i];
for(j=i+1;j<n;j++)
{
if(a[j]>right_max[i])
right_max[i]=a[j];
}
}
for(i=0;i<n;i++)
{
left_max[i]=a[i];
for(j=i;j>=0;j–)
{
if(a[j]>left_max[i])
left_max[i]=a[j];
}
}
for(i=0;i<n;i++)
{
s=s+(min(left_max[i],right_max[i])-a[i]);
}
cout<<s;
return 0;
}

#2

@lovish2552
Your function for find max is inefficient
Have a look at the code here
You can optimise your right max and left max to 0(1) instead of 0(n)

#3

It means due to complexicity my code is facing some errors because array size is too large?

#4

@lovish2552
You got TLE
That’s because of complexity of code being O(n^2) instead of required O(n)
Kindly close the doubt

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.