The length of the maximum subarray, so the 1st element is larger than the last element

Question

I am given an array. I need to find the length of the maximum subarray in which the first element is greater than the last element. For example, 5 4 3 2 1. The length of the maximum subarray is 5, since the first element 5 is greater than the last element 1. Another example: 5 10 4 7 9 8. The length is 5 again, and the array starts at 10 and reaches the last element. I know a naive approach, i.e. O (n²), but needs a more efficient approach.

Answer 1

Here is the linear O (n) algorithm:

Algorithm description

First, collect all the indices i for which the following is true:

For any j> i: a _i <a <sub> Jsub>

Thus, they are a kind of minima in the sense that to the right of them is not less or equal.

Keep a link to the left most, call this index j. This variable will be used as the ending index of the (inclusive) range.

Now we start on the left with index i, and as soon as _i > a _j , we move on to the next “minimum” (therefore j increases), while this condition holds (a _i > a _j ). For the last j where it runs: this might be the solution: make sure that this is the longest range found so far.

Whenever j <i, also take the following “minimum”

Whenever there are no more lows, stop the algorithm.

Visual presentation

The idea is presented here in a graphical representation of the values ​​of the array, where the red marks are the minima and the green markers are possible candidates for where the auxiliary decision array can begin:

The code

Here is the implementation of this algorithm in JavaScript: you can enter the values ​​of the array, and the largest auxiliary array will be displayed as you type:

function longestSubArray(a) { // Preprocessing: collect all i, for which holds: // if j > i, then a[i] < a[j] var minima = [-1] // Add a special value first (see later) var last = Infinity; for (var i = a.length - 1; i >= 0; i--) { if (a[i] < last) { last = a[i]; minima.push(i); // Optimisation: It is of no use to find more minima if // this value is less than the first value in the aay if (last < a[0]) break; } } // Get first value from minima. This will be the rightmost // value that is less than a[0], or if such does not exist, // the minimum value in the aay. var j = minima.pop(); var maxSize = 1; var maxStart = 0; // Look for ranges that start at i: for (i = 0; i < a.length; i++) { // Check if range (i, j) fulfills the requirement while (j !== -1 && (a[i] > a[j] || j <= i) ) { // Check if range (i, j) is the largest so far if (j - i + 1 > maxSize) { maxSize = j - i + 1; maxStart = i; } // Take an end index that is more to the right, // but which will represent a higher value also: j = minima.pop(); // could be -1: which means "all done" } if (j == -1) break; } if (maxSize == 1) return []; // no solution return a.slice(maxStart, maxStart+maxSize); } // I/0 handling -- not relevant to the algorithm: var input = document.querySelector('input'); var output = document.querySelector('span'); input.oninput = function () { // Translate text input to aay of integers var a = input.value.match(/-?\d+/g).map(Number); // Apply function var sub = longestSubArray(a); // Output result output.textContent = sub.join(' '); } 

 Enter array: <input size="60"><br> Longest sub-array: <span></span> 

See here for the same function in Python.

Proof of the complexity of linear time

The algorithm has linear time complexity:

• The cycle for collecting minima is repeated no more than n times
• Loop at iteration i no more than n times
• The inner loop will generally be repeated no more than n times, although it could iterate more than once on i, the minimum array minima are reduced at each iteration.

So: O (n).

Answer 2

You can try applying the caterpillar method, which will be O (n):

The idea is to use two indexes: one for the head and the other for the tail, as well as a variable maximum length. Then you try to advance the head until the condition is valid: the minimum value in the subsequence from the head to the end of your array is less than the tail value.

If you cannot advance your head because the condition is not fulfilled, then you are promoting the tail. Thus, it resembles a caterpillar that propels its head and then its tail as it moves.

This minimum can be previously calculated in the previous iteration over the array.

This is a possible implementation in python:

 def subSeqLen(arr): head = 0 tail = 0 maxLength = 0 minFromLast = [arr[-1]]*len(arr) for i in xrange(len(arr)-2, -1, -1): minFromLast[i] = min(minFromLast[i+1], arr[i]) while head >= tail and head < len(arr): if arr[tail]>arr[head] and head-tail+1 > maxLength: maxLength = head-tail+1 if head < len(arr)-1 and minFromLast[head+1]<=arr[tail]: head += 1 else: tail += 1 head = max(head, tail) return maxLength 

Answer 3

Create another array of pairs so that the first element is the same as your array and the second is the index of the element, so for the array:

5 4 3 2 1

The new array will be like

 5,1 4,2 3,3 2,4 1,5 

Now sort the array of pairs so that it looks like this:

 1,5 2,4 3,3 4,2 5,1 

Now create a Segment Tree using the indices of a sorted array of pairs.

Now iterate over the array and for each element find it equivalent in the sorted array (this can be done in O (1)), suppose that the indices j, you know, perform a range query in the [1, i] segment (since all the elements in the [ 1, i] lower than the current element, because the array of pairs is sorted) to find the maximum index value in log (n), and finally, the answer is the maximum value among all segment lengths.

Complexity is O (nlog (n)).

Answer 4

EDIT: There seems to be a very simple O (n) solution.

---

To solve the problem, you can use two algorithms:

Binary-search, Stack, O (n * log (n))

Let's take a few j and consider all valid subarrays ending with an element in the jth position. The answer will be i such that a [i]> a [j] and I <J . Iterating over all such i will give us complexity O (n ² ) .

There is one simple idea to keep in mind in order to improve complexity. If we have i ₁ and a [i ₁ ] , we will never consider another i ₂ as the starting point of a valid subarray when i ₁ <i ₂ and a [i ₁ ]> a [i ₂ ] , because i ₁ gives best result. Saves such pairs (a [i], i) in the data structure d .

At any moment in time, d will look like (a [i ₀ ], i ₀ ), (a [i ₁ ], i ₁ ) ... (a [i _n ], i _n ) . Both i _p and a [i _p ] increase from left to right.

When we consider the next j as the end of a valid subarray, we can search for the current best answer in d . All i -s in d are below the current j . We should look for the left pair (a [i], i) , where a [i]> a [j] gets j - i + 1 as the current answer. Since pairs are sorted, we can use binary search.

In the case of a [j] the most a [i] of d , then we have a new pair (a [j], j) is added to d .

 ans <- 0 d <- [] // contains (val, idx) structures for j = 0..n-1 l <- 0, r <- len(d) - 1 while l <= r mid = (l + r) / 2 // integer division if d[mid].val > a[j] r <- mid - 1 else l <- mid + 1 if l = len(d) append (a[j], j) to d else curAns <- j - d[l].idx + 1 ans <- max(ans, curAns) 

The overall complexity is O (n * log (n)) .

Segment Tree, O (n * log (n))

Take a look at the answer of Abdenaceur Lichiheb

There are no limits on the limits of a , since they can be easily sorted and then mapped to indices in a sorted array.