## Maximum Difference in an Array

You are given an array of integers and must compute the maximum difference between any item and any lower indexed smaller item for the possible pairs, i.e., for a given array *a* find the maximum value of *a[j] – a[i] for all i, j where 0 <= i < j < n* and *a[i] < a[j]*. If no item has smaller item with lower index then return -1.

For example given an array [1, 2, 6, 4]. you will first compare 2 to the elements to its left. 1 is

**Functional Description**

Complete the function *maxDifference *. The function must return an integer representing the maximum difference in *a*.

*maxDifference has the following parameter(s): a[a[0],a[1],……a[n-1]]: an array of integers*

**Constraints **

- 1 <= n <= 2 x 10^5
- -10^6 <= a[i] <= 10^ 6

#### **Solution **

- One way is to compare every 2 keys and look if this is the maximum difference so far and update max difference. The complexity of this solution will be
*O(n^2)* - Another way is to iterate from the beginning and keeping track of maximum difference and minimum value so far if the difference between the current item and the minimum value is more than update maximum. The complexity of this solution will be
*O(n)*

This code was asked in YapStone HackerRank Test. Please comment if you encountered this question somewhere. Mail us Interview questions and Experiences at [email protected]