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