Maximum Difference Between Two Elements Such that Larger Element Appears After the Smaller Number

Problem

Find the maximum difference between two array elements such that the bigger element appears after, the smaller.

Brute Force approach

Utilize two loops. Pick items one by one in the outer loop and in the inner loop, compute the difference between the selected element and every other element in the array and compare the difference to the largest difference determined so far.  This takes O(N 2 ) time. Can we do better? Let’s see!

Efficient approach

In this technique, instead of taking the difference between the selected element and every other element, we take the difference between the selected element and the smallest element found thus far. So we must keep two things on track:

1. The greatest difference discovered thus far.
2. The smallest number of elements viewed so far.

This approach takes only O(N) time and O(1) space.

C Programming

#include<stdio.h>
int solve(int arr[], int n)
{
int ans = arr[1] - arr[0];   //keep track of answer
int minElement = arr[0];  //keep track of minimum element
int i;
for(i = 1; i < n; i++)
{   
    if (arr[i] - minElement > ans)        //update answer                  
    ans = arr[i] - minElement;
    if (arr[i] < minElement)
        minElement = arr[i];                    
}
return ans;
}

void main(){
    int a[]={1, 2, 3, 4, 7, 3, 5};
    int n = sizeof(a)/sizeof(a[0]);
    printf("%d",solve(a, n));
}

Output

6

C++ Programming

#include <bits/stdc++.h>
using namespace std;

int solve(int arr[], int n)
{
     // max difference 
     int ans = arr[1] - arr[0];
      
     // minimum element
     int minElement = arr[0];
     for(int i = 1; i < n; i++)
     {    
       if (arr[i] - minElement > ans)                            
       ans = arr[i] - minElement;
        
       if (arr[i] < minElement)
       minElement = arr[i];                    
     }
      
     return ans;
}

int main(){
    int a[]={1, 2, 3, 4, 7, 3, 5};
    int n = sizeof(a)/sizeof(a[0]);
    cout<<solve(a, n);
}

Output

6

Python Programming

def solve(arr, n):
    ans = arr[1] - arr[0]  #keep track of difference
    minElement = arr[0]    #keep track of minimum element
    
    for i in range( 1, n ):
        if (arr[i] - minElement > ans):  #update answer
            ans = arr[i] - minElement
    
        if (arr[i] < minElement):
            minElement = arr[i]
    return ans

l = [1, 2, 3, 4, 7, 3, 5]

n = len(l)

print(solve(l,n))

Output 6 People are also reading:

• Subarray with Sum k
• Rearrange an array in maximum minimum form
• Find Maximum Subarray Sum
• Find whether an array is subset of another array
• Maximum Sum Circular Subarray
• Rod Cutting Problem – Dynamic Programming
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Print a given matrix in spiral form
• Replace Every Array Element With The Product of Every Other Element
• Maximum of all Subarrays of size K