title: Find the largest possible difference in an array with the smaller integer occurring earlier
body: <p>This is an interview question: </p>
  
  <p>Find the largest possible difference in an array of integers, such that the smaller integer occurs earlier in the array.</p>
  
  <p>Constraint:
  Numbers are not unique.
  The range is Integer range of java. (or any other language)</p>
  
  <p>Example:</p>
  
  <p>input 1: {1, 100, 2, 105, -10, 30, 100}</p>
  
  <p>The largest difference is between -10 and 100 -> 110 (here -10 is at the 5th index and 100 is at 7th index)</p>
  
  <p>input 2: {1, 100, 2, 105, -10, 30, 80}</p>
  
  <p>The largest difference is between 1 and 105 -> 104 (here 1 is at the 1st index and 105 is at 4th index)</p>
  
  <p>Possible Solution:</p>
  
  <p>One approach is check for all possible differences and keep a track of the biggest difference found till now  O(n^2) complexity.</p>
  
  <p>can this be done in better than O(n^2) time? </p>