i have tried writing my own max function to till using stl function to find right maximum element. i am calling that function only when we have i is at maximum element of array still i am failing test case due to time limit i mean even if i pre compute(right maximum element in another array) the complexity should be same as a for loop under the max will be needed,even here i am doing same using max function a for loop … so why these are failing testcase due to time limit…
//header files commented as the text was getting bigger
//#include
//#include
using namespace std;
int big(int *arr,int curr,int n)
{ int ind_big=curr;
for(int i=curr;i<n;i++)
if(arr[i]>=arr[ind_big])
ind_big=i;
return ind_big;
}
int main() {
int n;
int sum=0;
int prev=0;
int right=-1;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++)
cin>>arr[i];
for(int i=0;i<n;i++){
if(i==0||i==n-1)
if (arr[i]==0)
{
right=distance(arr, max_element(arr, arr+n));
continue;
}
//base check done
if(arr[i]<arr[prev])
{
if(i>=right){
// right=big(arr,i,n);
right=distance(arr, max_element(arr+i, arr+n));
}
sum+=arr[prev]<arr[right]?arr[prev]-arr[i]:arr[right]-arr[i];//minimum of both must be level
}
else{
prev=i;
}
// cout<<sum<<" "<<prev<<" "<<right<<endl;
}
cout<<sum;
return 0;
}