#### Arrays & Strings

**Problem **

Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array.

For e.g, consider the array ** { 3, 2, 6, 9, 5 } **.

Maximum difference between 2 elements in the array is **7** ( 9 – 2 ) & **9** appears after **2** in the array.

**Solution **

Maintain two variables storing **maximum difference** obtained so far and the **minimum** element seen till now.

Iterate over the array & for all **i = 1 … n-1**, find the **diff = arr(i) – minimum**. Update the **max diff** and **min element** as you iterate over the array.

See the implementation below.

#include<iostream> using namespace std; // max difference of two elements in the array // s.t. larger element appears after the smallest // element in the array int maxDiff(int arr[],int size) { int i; int max_diff = arr[1]-arr[0]; int min_element = arr[0]; for (i=1;i<size;i++) { if (arr[i] > min_element) { // diff of current and min element int diff = arr[i]-min_element; if (diff > max_diff) { // update max diff max_diff = diff; } } else { // update the min element in the array min_element = arr[i]; } } return max_diff; } // main int main() { int arr[] = { 1,4,-2,6,-1,2,7,3,19,-6,11,1 }; int size = sizeof(arr)/sizeof(arr[0]); int max_diff = maxDiff(arr,size); cout<<"\nMax difference :: "<<max_diff; cout<<endl; return 0; }