Help for solving this subarray inversion problem

general
, , , ,
#1

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.

#2

[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.

Here is the


[2].


  [2]: http://ideone.com/6kyobB
2 Likes
#3

@meooow
I understood the coordinate compression thing and making the last occurrence array. But I didn’t understand anything beyond that.

what does this mean “Generate a prefix max array pp on this last occurrence array.”

1 Like
#4

@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.

#5

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.

@meooow, can you clarify here, please :slight_smile:

1 Like
#6

I also think that @meooow has misinterpreted the question as he is taking all the value from i to j in sub-array such that A[i]>=A[j]

#7

Quite Possible.

#8

I have replaced the sort of ambiguous line about the last occurrence, thanks for pointing it out. The answer is quite correct though, @bansal1232.

1 Like
#9

@meooow
can you please explain this part p[A[i]]−i+1. what does this statement mean and what are we trying to achieve using this statement.

#10

@arpit728 I have edited the answer, please tell me if it is clearer now :slight_smile:

#11

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.

Thank you very much.