You are given an array consisting of N integers. Now, you need to find the length of largest sub array of this array where first element of this sub array is ≥ than the last element of that sub array.
Let us consider a sub array from index i to j. You need to find the length of the maximum length sub array, such that A[i]≥A[j].
Sample Input:
The first line contains a single integer T denoting the number of test cases in a single test file. Each test case is spread over 2 lines, in the following format :
The first line of each test case contains a single integer N denoting the size of the given array A. The next line contains N space separated integers, where the ith integer denotes A[i].
Sample Output:
For each test case output answer in new line.
Constraints:
1≤T≤10
1≤N≤105
−109≤A[i]≤109
Example test case:
Input:
1
5
5 4 3 2 1
Output :
5
Explanation:
The max length sub array which can be chosen is from index 1 to 5.
[Rewrote the answer, I hope this is easier to understand :)]
First we apply coordinate compression on the values in array A. Now all values are within the bound of 10^5. This will be helpful because we will need to use the values in A as array indices. We will use an array last that will store the last occurrences of each value in A. So last[v] will contain the last index at which v occurs in A. If it does not occur in A, we can set last[v]=-1. This can be done with a loop in linear time.
Now suppose we are at an index i of array A, then last[A[i]] contains the last index at which A[i] occurs. So last[A[i]]-i+1 will be the length of the longest subarray that starts at i with A[i] and also ends with A[i].
However the problem statement says that the last value of the subarray can be any value \le A[i], not just A[i] itself. So the length of the longest subarray starting at i with A[i] and ending with some value smaller than A[i] would be max(last[0], \; last[1], \; ... last[A[i]-1], \; last[A[i]]) - i + 1 . Running a loop from 0 to A[i] for each i will be too slow. So we need a smarter way.
We will make another array pre (reusing the same array is also possible) such that pre[v] will contain the last index of any value \le v. So pre[v]=max(last[0],\;last[1],\;...last[v-1],\;last[v]). We can do this in linear time again, using the following loop
p[0] = last[0]
for i in [1,n)
p[i] = max(p[i-1], last[i])
Now the only part left is to iterate over array A and find the answer. For index i, pre[A[i]]-i+1 will be the length of the longest subarray that starts at i with A[i] and ends with a value \le A[i]. Choose the maximum such value as answer.
@meooow i think you should count for first occurrence of each integer if you are running a loop from backward so that maximum distance can be achieved.
Maybe by last occurance @meooow meant “last occurance from w.r.t front” (or “first occurance from last”), cause I didn’t felt the anomaly until you pointed it out @bansal1232.
Hey! @meooow, It had been a great help and got to learn new concept of coordinate compression. Can you share some more cooler problems based on the same concept.
