#include <iostream>

using namespace std;

int max_diff_pair1(int *nArray, int n) {
  int maxDiff = 0;

  if(nArray==NULL || n<2)
    return maxDiff;

  for(int i=0; i<n; i++) {
    for(int j=i; j<n; j++) {
      if(nArray[i]-nArray[j]>maxDiff) {
	maxDiff = nArray[i]-nArray[j];

	//	cout << nArray[i] << "\t" << nArray[j] << endl;
      }
    }

  }

  return maxDiff;
}

int max_diff_recursive(int *start, int *end, int *max, int *min) {
  if(end==start) {
    *max = *min = *start;
    return 0x80000000;
  }

  int *middle = start + (end-start)/2;
  int maxLeft, minLeft;
  int leftDiff = max_diff_recursive(start, middle, &maxLeft, &minLeft);

  int maxRight, minRight;
  int rightDiff = max_diff_recursive(middle+1, end, &maxRight, &minRight);

  int crossDiff = maxLeft - minRight;

  *max = (maxLeft>maxRight?maxLeft:maxRight);
  *min = (minLeft<minRight?minLeft:minRight);

  int maxDiff = (leftDiff>rightDiff?leftDiff:rightDiff);
  maxDiff = (maxDiff>crossDiff?maxDiff:crossDiff);

  //cout << "max: " << *max << "; min:: " << *min << "; maxDiff: " << maxDiff << endl;

  return maxDiff;
}

int max_diff_pair2(int *nArray, int n) {
  if(nArray==NULL || n<2)
    return 0;

  int max, min;
  return max_diff_recursive(nArray, nArray+n-1, &max, &min);
}

int max_diff_pair4(int *nArray, int n) {
  if(nArray==NULL || n<2)
    return 0;

  int max = nArray[0];
  int maxDiff = max-nArray[1];

  for(int i=2; i<n; i++) {
    if(nArray[i-1]>max)
      max = nArray[i-1];

    int currentDiff = max-nArray[i];
    if(currentDiff>maxDiff)
      maxDiff = currentDiff;
  }

  return maxDiff;

}

int main(int argc, char **argv) {

  int array[] = {2, 4, 1, 16, 7, 5, 11, 9};

  cout << max_diff_pair1(array, 8) << endl;

  cout << max_diff_pair2(array, 8) << endl;

  cout << max_diff_pair4(array, 8) << endl;

  return 0;
}