# Maximum Difference in An Array

0
620

## Maximum Difference in An Array

Find the difference between any two elements in an array arr[] of integers such that the larger element appears after the smaller number in the array.

For example, if the array contains the elements [2, 3, 8, 6, 4, 8, 1], the returned value should be 6. (Diff between 8 and 2). The returned value should be 8 if the sequence is [ 7, 9, 5, 6, 13, 2 ]. (Diff between 5 and 13)

### 1st method (Brute Force) Maximum Difference in An Array

Make use of two loops. Pick elements one by one in the outer loop, then calculate the difference between the selected element and every other element in the array in the inner loop and add it to the maximum difference measured so far.

Complexity of Time: O (n2)

### Method number 2 – Maximum Difference in An Array

Instead of comparing the selected element to any other element, we use this approach to compare it to the smallest element found so far. As a result, we must keep track of two things:
1) So far, the greatest difference has been discovered.
2) The smallest number of people who have been so far.

`int` `maxDifference(int` `arr[], int` `n)`
`{`
`int` `min_element=arr;`
`int` `diff=arr-arr;`
`for(i=1;i<n;i++)`
`{`
`if(arr[i]-min_element>diff)`
`diff=arr[i]-min_element;`
`if(arr[i]<min_element)`
`min_element=arr[i];`
`}`
`return` `diff;`
`}`

Time Complexity: O(n)

Array Data Structure