title: How to find the maximum span of a given array of numbers?
body: <p>The problem I am trying to solve is the following : I want to find a maximum span of numbers in a given array that is given an array A consisting of both positive and negative integers return the largest (A[j] - A[i]) such that 1&lt;= i &lt; j &lt;= n, and I came up with the following nlogn time algorithm for this problem -:</p>
  
  <ol>
  <li>find the index of the nth order statistic of the array let it be "i"</li>
  <li>find the index of the 1st order statistic of the array let it be "j"</li>
  <li>if i > j, then return the difference because we found the difference between the maximum and the minimum elements of the array and hence just terminate returning the difference.</li>
  <li>if j > i then divide the array into two halves and find the maximum span in the 2 halves i.e A[1....i] and A[i + 1 ...... n] by calling this algorithm recursively, the case being when the algorithm finds such a pair i,j it returns the difference between those pairs, otherwise it keeps recursing and in the end terminates.</li>
  <li>return the maximum{max_span of subarray 1 , max_span of subarray2}</li>
  </ol>
  
  <p>This algorithm is O(nlogn) but I don't know if its correct or not.</p>