Max Distance

https://www.interviewbit.com/old/problems/max-distance/

 brute force:

int Solution::maximumGap(const vector<int> &A) {
    int ans;
    for(int i=0;i<A.size();i++){
        for(int j=0;j<A.size();j++){
            if(A[i] <= A[j])
              ans=max(ans,j - i);
        }
    }
    return ans;
}

2nd method:

int Solution::maximumGap(const vector<int> &A) {
    int n=A.size();
    if(n==1) return 0;
    vector<pair<int,int> >v;
    for(int i=0;i<n;i++){
        v.push_back(make_pair(A[i],i));
    }
    sort(v.begin(),v.end());
    int ans=0;
    int rmax=v[n-1].second;
    for(int i=n-2;i>=0;i--){
        ans=max(ans,rmax-v[i].second);
        rmax=max(rmax,v[i].second);
    }
    return ans;
}

3rd method:

int Solution::maximumGap(const vector<int> &v) {
    int n=v.size();
    vector<int> left(n+1);
    vector<int>right(n+1);
    left[0]=v[0];
    for(int i=1;i<n;i++){
        left[i]=min(left[i-1],v[i]);
    }
    right[n-1]=v[n-1];
    for(int i=n-2;i>=0;i--){
        right[i]=max(right[i+1],v[i]);
    }
    int x=0,y=0,ans=0;
    while(x<n && y<n){
        if(right[y]>=left[x]){
            ans=max(ans,y-x);
            y++;
        }
        else{
            x++;
        }
    }
    return ans;
}