title: Divide and Conquer to find maximum difference in an array
body: <p>I am trying to solve a problem where given an array I need to calculate the maximum difference such that the larger element appears after the smaller element. </p>
  
  <p><strong>Here is a better problem statement</strong>:</p>
  
  <p><em>Given the stock prices on each day for <code>n</code> days, what is the maximum profit a person can make by doing exactly one transaction. One transaction means that the person can buy exactly one stock on one day and sell it on a later date.</em></p>
  
  <p>I am trying to solve this problem using divide and conquer algo. </p>
  
  <p>In my recursive function i am trying to spilt the array into two halves, but i am not sure on how to proceed with logic. Do i just get the max difference in each halves and compare?</p>
  
  <pre><code>int calculateMaxDiff(int *src, int start, int end){
      if(end - start == 1) return src[start];
  
      int middle = (start + end)/ 2;
      int half1_diff;
      int half2_diff;
      half1_diff = calculateMaxDiff(src, start, middle);
      half2_diff = calculateMaxDiff(src, middle, end);
  
      //Do i need to have two loops here that calculate the diffs for each halves
      .... 
      return max(half1_diff, half2_diff);
   }
  </code></pre>
  
  <p>Edit: <strong>Example output</strong></p>
  
  <p>Give an array {12, 9, 18, 3, 7, 11, 6, 15, 6, 1 ,10} should return 12 as a result of difference between 15 and 3</p>