## 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

- Initialize the current_difference as the difference of the first two elements.
- 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; }

#### Java Program

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

### Complexity Analysis for Maximum difference between two elements

**Time Complexity: **O(N) where N is the size of the array. Here we apply the Kadane algorithm concept that will take O(n) time complexity.

**Space Complexity:** O(1) because we don’t use auxiliary space here. By the use of a few variables, we find the answer.

**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; }

#### Java Program

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

### Complexity Analysis for Maximum difference between two elements

**Time Complexity:** O(N^{2}) where N is the length of the given array. Here we check the largest element on the right side for each element that will take O(n*n) time complexity.

**Space Complexity:** O(1) because we just update the answer in a variable. We use a constant amount of space here.