I found this problem today and eventually came up with a solution. I'm interested in knowing other ways to solve it. You have a list of unsorted integers, and have to compute the greatest difference between list[j] - list[i] such that i < j.
Here's my code:
#include <stdio.h>
// remember the minimum to the left
static int _cached_max(int min, int n, int const* list)
{
if(n < 1){
return 0x80000000;
}
int max_index = 0;
for(int i = 1; i < n; ++i){
if(list[i] >= list[max_index]){
max_index = i;
}
}
// I know you can check this condition inside the loop above by keeping
// some extra variables, keeping it here for readability
for(int i = 0; i < max_index; ++i){
if(list[i] < min){
min = list[i];
}
}
int this = list[max_index] - min;
int next = _cached_max(min, n - max_index - 1, list + max_index + 1);
return this > next ? this : next;
}
int custom_max(int n, int const* list)
{
return _cached_max(list[0], n - 1, list + 1);
}
int main(int argc, char* argv[])
{
int list[] = {12,21,10,20,9,18};
int max = custom_max(sizeof list / sizeof list[0], list);
printf("max = %d\n", max);
return 0;
}
What is the optimal solution to this problem?
Update:
Here's some sample inputs and outputs:
F( [10;4;5;0;8] ) = 8
F( [10;7;16;5;11;3;9;0] ) = 9
F( [4;5;0;1;2;3;1;8] ) = 8
F( [12;21;10;20;9;18] ) = 10
F( [5;4] ) = -1
