Maximum difference between two elements such as larger element comes after smaller

Problem Statement

We have given an array of n integers in which we have to find the maximum difference between two elements such as larger element comes after smaller.

Example

Input

4  7  2  18  3  6  8  11  21

Output

19

Approach 1 for Maximum difference between two elements 

We make use of the Kadane’s approach in a modified form.

Algorithm

1. Initialize the current_difference as the difference of the first two elements.
2. Loop through the array such that

• If the current_difference is greater than zero then add to it the difference of the consecutive array elements.(Compute Prefix Sum).
• Else current_difference is equal to the difference of the present consecutive elements.
• Compare the current_difference with the present max_difference and update it accordingly.

The approach uses Dynamic Programming and is very efficient.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{  
  int arr[] = {4,5,8,1,3,7,11,13,2};
  int N = sizeof(arr)/sizeof(arr[0]);  
  
  int diff = arr[1]-arr[0];
  int curr_sum = diff;
  int max_sum = curr_sum;
 
  for(int i=1; i<N-1; i++)
  {
    // Calculate current diff
    diff = arr[i+1]-arr[i];
 
    // Calculate current sum
    if (curr_sum > 0)
      curr_sum += diff;
    else
      curr_sum = diff;
 
    // Update max sum, if needed
    if (curr_sum > max_sum)
      max_sum = curr_sum;
  }
    
  if(max_sum >= 0)
    cout<<"Maximum difference is "<<max_sum<<endl;
  else
    cout<<"Maximum difference is not valid as array reversely sorted"<<endl;
  return 0;
}

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int diff = a[1]-a[0];
        int curr_sum = diff;
        int max_sum = curr_sum;
        for(int i=1;i<n-1;i++)
        {
          // Calculate current diff
          diff = a[i+1]-a[i];
          // Calculate current sum
          if (curr_sum > 0)
            curr_sum += diff;
          else
            curr_sum = diff;
          // Update max sum, if needed
          if (curr_sum > max_sum)
            max_sum = curr_sum;
        }
        if(max_sum >= 0)
          System.out.println("Maximum difference is "+max_sum);
        else
          System.out.println("Maximum difference is not valid as array reversely sorted");
    }
}

9
4 5 8 1 3 7 11 13 2

Maximum difference is 12

Approach 2 for Maximum difference between two elements 

Algorithm

1. Loop From the last of the array as we will have to check the larger number occurs later.

2. Run another loop from start and do:

a) If the present element is smaller than the number present at the index of the outer loop, then check if its difference is larger than the present difference.If yes then update the max_difference.

b) Else increment the loop counter and check for the next difference.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{  
  int arr[] = {4,5,8,1,3,7,11,15,2};
  int N = sizeof(arr)/sizeof(arr[0]);  
  int max_diff = INT_MIN;
  
  for(int i=N-1; i>=0; i--) //start from the end so that we can check if the larger element comes later.
  {
    for(int j=0;j<i;j++) //select each number from start till one less than the number selected
    {
      if(arr[i] > arr[j]) //if the condition satisfies
      {
        if(arr[i] - arr[j] > max_diff) //update the max_diff
          max_diff = arr[i]-arr[j];
      }
    }
  }
  cout<<"Maximum difference is "<<max_diff<<endl;
  return 0;
}

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int max_diff = -1000000;
        for(int i=n-1; i>=0; i--) //start from the end so that we can check if the larger element comes later.
        {
          for(int j=0;j<i;j++) //select each number from start till one less than the number selected
          {
            if(a[i] > a[j]) //if the condition satisfies
            {
              if(a[i] - a[j] > max_diff) //update the max_diff
                max_diff = a[i]-a[j];
            }
          }
        }
        System.out.println("Maximum difference is "+max_diff);
    }
}

9
4 5 8 1 3 7 11 15 2

14