HackerEarth Zulu encounters a Sequence Problem solution

In this HackerEarth Zulu encounters, a Sequence problem solution Zulu is good in maths. He loves to play with numbers. One day while browsing through a book, he encountered a nice problem. In the problem, he was given an array A of N numbers.

For each index i in the array we define two quantities. Let r be the maximum index such that r >= i and sub-array from i to r (inclusive) is either non-decreasing or non-increasing. Similarly, let l be the minimum index such that l <= i and sub-array from l to i (inclusive) is either non-decreasing or non-increasing. Now, we define points of an index i to be equal to max(|Ai – Al|, |Ai – Ar|). Note that l and r can be different for each index i.

The task of the problem is to find the index of the array A which have the maximum points.

Since the problem seems a bit harder, Zulu is struck. Can you solve this problem for Zulu?

HackerEarth Zulu encounters a Sequence Problem solution.

#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd || g==-1){
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'n');
}
string readStringLn(int l,int r){
    return readString(l,r,'n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

int T;
int n;
long long arr[200200];

int main(){
    T=readIntLn(1,5);
    while(T--){
        n=readIntLn(1,200000);
        for(int i=0;i<n;i++){
            if(i==n-1){
                arr[i]=readIntSp(-2000000000,2000000000);
            } else {
                arr[i]=readIntSp(-2000000000,2000000000);
            }
        }
        getchar();
        long long sol=0;
        long long old;
        old=arr[0];
        for(int i=1;i<n;i++){
            if(arr[i]>=arr[i-1]){
                sol = max(sol,arr[i]-old);
            } else {
                old=arr[i];
            }
        }
        old=arr[0];
        for(int i=1;i<n;i++){
            if(arr[i]<=arr[i-1]){
                sol = max(sol,old-arr[i]);
            } else {
                old=arr[i];
            }
        }
        reverse(arr,arr+n);
        old=arr[0];
        for(int i=1;i<n;i++){
            if(arr[i]>=arr[i-1]){
                sol = max(sol,arr[i]-old);
            } else {
                old=arr[i];
            }
        }
        old=arr[0];
        for(int i=1;i<n;i++){
            if(arr[i]<=arr[i-1]){
                sol = max(sol,old-arr[i]);
            } else {
                old=arr[i];
            }
        }
        cout<<sol<<endl;
    }
    assert(getchar()==-1);
}

coding problems solutions