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

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

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)