CareerCup

There is a nice explanation for the linear time solution of this problem on geeksforgeeks

www.geeksforgeeks.org/given-an-array-arr-find-the-maximum-j-i-such-that-arrj-arri

This is how I'd do it
optimizations
1: always start j after i so that we don need to check for i<j
2: i will always be less than size-max so that there is always a array that is larger than max to check for
3: j should start after i but also i+max so that the length of a[i], a[j] in comparison will never be smaller than max

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    
    System.out.print("Enter the size of arr : ");
    int size = in.nextInt();
    
    int[] arr = new int[size];
    for (int i = 0; i < size; i++) arr[i] = in.nextInt();
    
    int max=0;
    for(int i=0;i<size-max;i++)
        for(int j=i+max+1;j<size;j++)
            if (arr[i]<arr[j]&&j-i>max)
                max=j-i;

    System.out.println("the max length between a[i],a[j] where a[i]<a[j] is "+max);
}

unsigned int max_distance(const int arr [], unsigned int sz )
{

unsigned int gmax = 0;

if(sz <= 1)
return 0;

int prev = arr[0];

for(int i = 0; i < sz; i++ )
{
if(arr[i] > prev){
std::cout << "skipped " << arr[i] << "@ i = " << i << "\n";
continue;
}
unsigned int mdist=0;
for(int j = i; j < sz; j++)
{
if(arr[i] < arr[j])
mdist = (j-i);
}

prev = arr[i];
gmax = (gmax < mdist ? mdist : gmax);
}

return gmax;
}

unsigned int max_distance(const int arr [], unsigned int sz )
{
    
    unsigned int gmax = 0;
    
    if(sz <= 1)
        return 0;
        
    int prev = arr[0];
        
    for(int i = 0; i < sz; i++ )
    {
        if(arr[i] > prev){
          std::cout << "skipped " << arr[i] << "@ i =  " << i << "\n";
          continue;
        }
        unsigned int mdist=0;
        for(int j = i; j < sz; j++)
        {
            if(arr[i] < arr[j])
                mdist = (j-i);
        }

        prev = arr[i];
        gmax = (gmax < mdist ? mdist : gmax);
    }   

    return gmax;
}

//Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.
//
//        For eg. 6, 9, 3, 2, 10, 2, 3
//


import java.util.Scanner;
import java.util.stream.Stream;

public class ArrayMinMaxDistance {

    private final int[] inputArray;

    public ArrayMinMaxDistance(int[] input) {
        this.inputArray = input;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter array");
        int[] input = Stream.of(scanner.nextLine().split(", ")).mapToInt(Integer::parseInt).toArray();

        ArrayMinMaxDistance arrayMinMaxDistance = new ArrayMinMaxDistance(input);

        int output = arrayMinMaxDistance.findMaxDistance();
        System.out.println(output);
    }

    private int findMaxDistance() {
        int inputArrayLength = inputArray.length;
        int[] minElementArray = new int[inputArrayLength];
        int[] maxElementArray = new int[inputArrayLength];

        minElementArray[0] = inputArray[0];
        for (int i = 1; i < inputArrayLength; i++)
            minElementArray[i] = Math.min(minElementArray[i-1], inputArray[i]);

        maxElementArray[inputArrayLength - 1] = inputArray[inputArrayLength - 1];
        for (int i = inputArrayLength - 2; i >= 0; i--)
            maxElementArray[i] = Math.max(maxElementArray[i+1], inputArray[i]);

        int minIndex = 0;
        int maxIndex = 0;
        int maxDistance = 0;
        while(minIndex < inputArrayLength && maxIndex < inputArrayLength) {
            if(minElementArray[minIndex] > maxElementArray[maxIndex]) {
                minIndex++;
            }
            else {
                maxDistance = Math.max(maxDistance, maxIndex - minIndex);
                maxIndex++;
            }
        }
        return maxDistance;
    }
}

//Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.
//
//        For eg. 6, 9, 3, 2, 10, 2, 3
//


import java.util.Scanner;
import java.util.stream.Stream;

public class ArrayMinMaxDistance {

    private final int[] inputArray;

    public ArrayMinMaxDistance(int[] input) {
        this.inputArray = input;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter array");
        int[] input = Stream.of(scanner.nextLine().split(", ")).mapToInt(Integer::parseInt).toArray();

        ArrayMinMaxDistance arrayMinMaxDistance = new ArrayMinMaxDistance(input);

        int output = arrayMinMaxDistance.findMaxDistance();
        System.out.println(output);
    }

    private int findMaxDistance() {
        int inputArrayLength = inputArray.length;
        int[] minElementArray = new int[inputArrayLength];
        int[] maxElementArray = new int[inputArrayLength];

        minElementArray[0] = inputArray[0];
        for (int i = 1; i < inputArrayLength; i++)
            minElementArray[i] = Math.min(minElementArray[i-1], inputArray[i]);

        maxElementArray[inputArrayLength - 1] = inputArray[inputArrayLength - 1];
        for (int i = inputArrayLength - 2; i >= 0; i--)
            maxElementArray[i] = Math.max(maxElementArray[i+1], inputArray[i]);

        int minIndex = 0;
        int maxIndex = 0;
        int maxDistance = 0;
        while(minIndex < inputArrayLength && maxIndex < inputArrayLength) {
            if(minElementArray[minIndex] > maxElementArray[maxIndex]) {
                minIndex++;
            }
            else {
                maxDistance = Math.max(maxDistance, maxIndex - minIndex);
                maxIndex++;
            }
        }
        return maxDistance;
    }
}

//Given an unsorted array find the maximum distance between two elements satisfying the condition A[i] < A[j] where i < j. There will always be a solution.
//
// For eg. 6, 9, 3, 2, 10, 2, 3
//

import java.util.Scanner;
import java.util.stream.Stream;

public class ArrayMinMaxDistance {

    private final int[] inputArray;

    public ArrayMinMaxDistance(int[] input) {
        this.inputArray = input;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter array");
        int[] input = Stream.of(scanner.nextLine().split(", ")).mapToInt(Integer::parseInt).toArray();

        ArrayMinMaxDistance arrayMinMaxDistance = new ArrayMinMaxDistance(input);

        int output = arrayMinMaxDistance.findMaxDistance();
        System.out.println(output);
    }

    private int findMaxDistance() {
        int inputArrayLength = inputArray.length;
        int[] minElementArray = new int[inputArrayLength];
        int[] maxElementArray = new int[inputArrayLength];

        minElementArray[0] = inputArray[0];
        for (int i = 1; i < inputArrayLength; i++)
            minElementArray[i] = Math.min(minElementArray[i-1], inputArray[i]);

        maxElementArray[inputArrayLength - 1] = inputArray[inputArrayLength - 1];
        for (int i = inputArrayLength - 2; i >= 0; i--)
            maxElementArray[i] = Math.max(maxElementArray[i+1], inputArray[i]);

        int minIndex = 0;
        int maxIndex = 0;
        int maxDistance = 0;
        while(minIndex < inputArrayLength && maxIndex < inputArrayLength) {
            if(minElementArray[minIndex] > maxElementArray[maxIndex]) {
                minIndex++;
            }
            else {
                maxDistance = Math.max(maxDistance, maxIndex - minIndex);
                maxIndex++;
            }
        }
        return maxDistance;
    }
}

I think this will work....
static int maxDistance(int[] arr) {
		if (arr == null || arr.length < 2)
			return -1;
		int start = 0;
		int end = arr.length - 1;

		while (start < end) {
			if (arr[start] < arr[end]) {
				return end - start;
			}
			end--;

		}
		return -1;
	}