Maximum difference between two elements

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

Examples: If array is [2, 3, 8, 6, 4, 8, 1] then returned value should be 6 (Diff between 8 and 2). If array is [ 7, 9, 5, 6, 13, 2 ] then returned value should be 8 (Diff between 5 and 13)

Method 1 (Brute Force)
Use two loops. In the outer loop, pick elements one by one and in the inner loop calculate the difference of the picked element with every other element in the array and compare the difference with the maximum difference calculated so far.

Time Complexity: O(n2)

Method 2

In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far.
2) Minimum number visited 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)

One Thought on “Maximum difference between two elements

  1. sampath on March 8, 2016 at 12:01 pm said:

    this problem is nothing but Stock Sell Maximize profit. Just use that logic here.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation