# Greatest difference between numbers in list

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

• (This question comes up every now and then, if at SO.) – greybeard Sep 25 '17 at 21:01
• @greybeard I guess it's the new fizzbuzz – Douglas Sep 25 '17 at 21:30
• 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. – Douglas Sep 27 '17 at 15:54

## 1 Answer

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;
}
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.1844555139541626, "perplexity": 7399.4831862613755}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-24/segments/1590347436466.95/warc/CC-MAIN-20200603210112-20200604000112-00226.warc.gz"}