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


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);
}