Distance Maximizing Problem O(n) http://leetcode.com/2011/05/a-distance-maximizing-problem.html

dmf.cc

#include <stdio.h>

int dmf(int *a, int n) {
	int *I = new int[n];
	int k=0;
	for (int i=0; i<n; ++i) {
		if (a[i] <= a[k]) {
			k = i;		}
		I[i] = k;
	}

	int i = (n-1), j;
	int max = 0;
	while (i >= 0) {
		k = I[i]; j=k;
		while (i > k) {
			while (a[i] > a[I[j-1]]) {
				j = I[j-1];
			}
			if (max < i - j) max = i - j;
			i = i - 1;		
		}
		i = j-1;
	}
	delete [] I;
	return max;
}

int main() {
	int A[8] = {6,5,9,15,1,6,4,7};
	printf("%d\n", dmf(A, 8));

}