Hey, so I recently started solving the problem of max distance in an array.
The problem statement is this:
Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].
My approach to this is the following:
Consider the index pairs: (1,n-1),(2,n-1),(3,n-1)......(n-1,n-1)
(1,n-2),(2,n-2),(3,n-2)...(n-2,n-2)
and so on...
While looping through these pairs keep storing the max distance and skip the rows where a result greater than max distance is not possible. So, if index pair (1,n-1) generates a result, then all rows below that are not capable of generating a solution greater than that.
Here is the code. A is the given array as a vector<int>
.
int si=0;
int ei=A.size()-1;
int res=-1;
while(ei>=0){
int temp=si;
while(((ei-temp)>res)&&(ei>=temp)){
if(A[ei]>=A[temp]){
res=ei-temp;
}
temp++;
}
ei--;
}
cout<<res<<endll;
I am solving this problem on interview bit[link] and it is showing a runtime error. Can somebody point out the flaw in this approach/code. I am not able to figure it out.
Thanks.