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?