Help for solving this subarray inversion problem

algorithm
array
dynamic-programming
optimization
sorting
#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*≥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*.

Sample Output:

For each test case output answer in new line.

Constraints:

  • 1≤T≤10
  • 1≤N≤105
  • −109≤A*≤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*] contains the last index at which A* occurs. So last[A*]-i+1 will be the length of the longest subarray that starts at i with A* and also ends with A*.
However the problem statement says that the last value of the subarray can be any value \le A*, not just A* itself. So the length of the longest subarray starting at i with A* and ending with some value smaller than A* would be max(last[0], \; last[1], \; ... last[A*-1], \; last[A*]) - i + 1 . Running a loop from 0 to A* 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* = max(p[i-1], last*)

Now the only part left is to iterate over array A and find the answer. For index i, pre[A*]-i+1 will be the length of the longest subarray that starts at i with A* and ends with a value \le A*. Choose the maximum such value as answer.

Here is the


[2].


  [2]: http://ideone.com/6kyobB
#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.”

#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:

#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*>=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.

#9

@meooow
can you please explain this part p[A*]−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.