#### 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;
}```