7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ (This question comes up every now and then, if at SO.) \$\endgroup\$ – greybeard Sep 25 '17 at 21:01
  • \$\begingroup\$ @greybeard I guess it's the new fizzbuzz \$\endgroup\$ – Douglas Sep 25 '17 at 21:30
  • \$\begingroup\$ There's a bug in the code above, the recursive call should check if the current max is less than the minimum and set it accordingly. \$\endgroup\$ – Douglas Sep 27 '17 at 15:54
2
\$\begingroup\$

Consider that the greatest difference of the following 2 sets exceeds the int range. For a more robust solution, return a wider type or detect failure.

{INT_MIN, INT_MAX}
{INT_MAX, INT_MIN}

// int custom_max(int n, int const* list)
long long custom_max(int n, int const* list)

Better to use size_t for array indexing. int may be too narrow.


A solution in liner time, as answered by @janos, is do-able, yet a few changes are needed to handle an ever decreasing list like {10,8,7,4,0}.

For each element arr[i] from 1 to n-1, find if the difference of that element and the prior minimum is a greater difference.

Then update the minimum.

// Detect rare cases when long long and int have similar ranges.
#include <limits.h>
#if LLONG_MIN/2 > INT_MIN || LLONG_MAX/2 < INT_MIN
#error Need wider type
#endif

long long custom_max(size_t n, int const* list) {
   if (n < 2) {
     // Handle pathological case.
     // Avoid magic number
     // return 0x80000000;
     return LLONG_MIN;
   }
   int min = list[0];
   long long maxdiff = LLONG_MIN;
   for (size_t i = 1; i < n; i++) { 
     long long diff = (long long) list[i] - min;
     if (diff > maxdiff) {
       maxdiff = diff;
     }
     if (list[i] < min) {
       min = list[i];
     }
   }
   return maxdiff;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.