algorithm - Recursion to get maximum difference in array -

return pair of numbers p , q in array. p must appear before q in array, , q-p must highest possible value

a=[1,4,12,5,9,1,3,8]

the return values p=1 & q=12

someone suggested below solution. not sure should return in 'third case' suggested below:

suggestion:

divide evenly 2 smaller arrays a1,a2, , solve problem (recursively) on a1 , a2. can find optimum on a? don't forget you're allowed use processing costing o(n).suppose p,q optimal pair a. either p,q∈a1, or p,q∈a2, or neither of these cases true. can in third case p , q?

below code divides array , minimum first half , maximum second half. there 0(n) solution interested in recursive 1 learning recursion. please don't suggest other solution.

    #define min_f(a, b) (a)>(b)?(b):(a)     #define max_f(a, b) (a)>(b)?(a):(b)     #define max 1 << 30     #define min -1      int get_min(int *a, int start, int end)     {             int t_min = max;             while(start <= end) {                     t_min = min_f(t_min, a[start]);                     start++;             }             return t_min;     }      int get_max(int *a, int start, int end)     {             int t_max = min;             while(start <= end) {                     t_max = max_f(t_max, a[start]);                     start++;             }             return t_max;     }      int foo(int *a, int start, int end)     {             int g_max = min;             int min, max, i;              for(i=0;i<=end;i++) {                     min = get_min(a, start, i);                     max = get_max(a, i+1, end);                     if (max > min) {                             g_max = max_f(g_max, max-min);                     }             }             return g_max;     }      int main()     {             int a[] = {1,4,12,5,9,1,3,8};             int size = sizeof(a)/sizeof(a[0]);             printf("%d\n", foo(a, 0, size-1));             return 0;     } 

your recursive solution nothing divide , conquer algorithm. can look-up binary-search algorithm understand basic concept of divide , conquer.

now, let take example.

                 [1,4,12,5,9,1,3,8]                        /\                       /  \                      /    \             [1,4,12,5]    [9,1,3,8] 

if did read above link, or know divide , conquer algorithm, understand recursively operation left sub-array , right-subarray. next step is, divide each of halves again. here, lets first half, sufficient third case, clueless about.

take first half, divide again.

                  [1,4,12,5]                      /\                     /  \                    /    \               [1,4]      [12,5] 

at step of dividing array, should have understood third case is. answer p = 1 (in left-half) , q = 12(in right-half) lie in different halves after division

this third case. now, leave write recursive code , take care of third case appropriately in code.