I have input array A
A[0], A[1], … , A[N-1] and T
I need solution O(N) for finding max size (j - i + 1) max(A[i…j]) - min(A[i…j]) <= T
Check it out this editorial
It is described here how to solve in O(N) more general problem of finding for each k the number of pairs (i,j) for which j-i+1=k and max(A[i…j]) - min(A[i…j]) <= T