The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

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 arrayint 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 elementint 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;
}
// mainint 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;
}

#include<iostream>using namespace std;
// max difference of two elements in the array
// s.t. larger element appears after the smallest
// element in the arrayint 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 elementint 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;
}
// mainint 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;
}