Maximum Difference in An Array

0
620

Maximum Difference in An Array

Maximum Difference in An Array
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[0];
int diff=arr[1]-arr[0];
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

Maximum Difference in An Array

LEAVE A REPLY

Please enter your comment!
Please enter your name here