Max Distance

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j]. Input Format

First and only argument is an integer array A. Output Format

Return an integer denoting the maximum value of j - i; Example Input

Input 1:

 A = [3, 5, 4, 2]

Example Output

Output 1:

 2

Example Explanation

Explanation 1:

 Maximum value occurs for pair (3, 4).

public class Solution {
    public int maximumGap(final int[] A) {
        if (A.length == 1)
            return 0;
        int maxDiff;
        int i, j;
        int RMax[] = new int[A.length];
        int LMin[] = new int[A.length];
        /*
         * Construct LMin[] such that LMin[i] stores the minimum value from (arr[0],
         * arr[1], ... arr[i])
         */
        LMin[0] = A[0];
        for (i = 1; i < A.length; ++i)
            LMin[i] = Math.min(A[i], LMin[i - 1]);
        /*
         * Construct RMax[] such that RMax[j] stores the maximum value from (arr[j],
         * arr[j+1], ..arr[n-1])
         */
        RMax[A.length - 1] = A[A.length - 1];
        for (j = A.length - 2; j >= 0; --j)
            RMax[j] = Math.max(A[j], RMax[j + 1]);
        /* Traverse both arrays from left to right to find optimum j - i */
        i = 0;
        j = 0;
        maxDiff = -1;
        while (j < A.length && i < A.length) {
            if (LMin[i] <= RMax[j]) {
                maxDiff = Math.max(maxDiff, j - i);
                j = j + 1;
            } else
                i = i + 1;
        }
        return maxDiff;
    }
}