Max Distance Asked in: Google Amazon Microsoft
Problem Description
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).
Solution:
class Solution:
# @param A : tuple of integers
# @return an integer
def maximumGap(self, A):
n=len(A)
R = [0] * n
R[n - 1] = A[n - 1]
for j in range(n - 2, -1, -1):
R[j] = max(A[j], R[j + 1]);
i = 0;j=0
diff = -1
while (j < n and i < n):
if (A[i] <= R[j]):
diff = max(diff, j - i)
j+=1
else:
i+=1
return diff
Comments
Post a Comment