StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>For brevity's sake I am going to assume all the elements are unique. The algorithm can be extended to handle non-unique element case.</p> <p>First, observe that if <code>x</code> and <code>y</code> are your desired max and min locations respectively, then there can not be any <code>a[i] > a[x]</code> and <code>i > x</code>, and similarly, no <code>a[j] < a[y]</code> and <code>j < y</code>.</p> <p>So we scan along the array <code>a</code> and build an array <code>S</code> such that <code>S[i]</code> holds the index of the minimum element in <code>a[0:i]</code>. Similarly an array <code>T</code> which holds the index of the maximum element in <code>a[n-1:i]</code> (i.e., backwards).</p> <p>Now we can see that <code>a[S[i]]</code> and <code>a[T[i]]</code> are necessarily decreasing sequences, since they were the minimum till <code>i</code> and maximum from <code>n</code> till <code>i</code> respectively.</p> <p>So now we try to do a merge-sort like procedure. At each step, if <code>a[S[head]] < a[T[head]]</code>, we pop off an element from <code>T</code>, otherwise we pop off an element from <code>S</code>. At each such step, we record the difference in the head of S and T if <code>a[S[head]] < a[T[head]]</code>. The maximum such difference gives you your answer.</p> <p>EDIT: Here is a simple code in Python implementing the algorithm.</p> <pre class="lang-python prettyprint-override"><code>def getMaxDist(arr): # get minima going forward minimum = float("inf") minima = collections.deque() for i in range(len(arr)): if arr[i] < minimum: minimum = arr[i] minima.append((arr[i], i)) # get maxima going back maximum = float("-inf") maxima = collections.deque() for i in range(len(arr)-1,0,-1): if arr[i] > maximum: maximum = arr[i] maxima.appendleft((arr[i], i)) # do merge between maxima and minima maxdist = 0 while len(maxima) and len(minima): if maxima[0][0] > minima[0][0]: if maxima[0][1] - minima[0][1] > maxdist: maxdist = maxima[0][1] - minima[0][1] maxima.popleft() else: minima.popleft() return maxdist </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload