title: Divide and Conquer Algorithm for Finding the Maximum Subarray - How to also provide the result subarray indexes?
body: <p>Excuse me, I have an assignment to solve the <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow">Maximum Sub Array Problem</a> using the <a href="https://copingwithcomputers.com/2014/05/17/maximum-subarray-problem/" rel="nofollow">Brute Force Algorithm O(n^2)</a>, <a href="http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/" rel="nofollow">Divide and Conquer O(nlogn)</a> and <a href="http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/" rel="nofollow">Kadane's Algorithm O(n)</a>. (My code is different).</p>
  
  <blockquote>
    <p>"<em>For example, for the sequence of values <code>{−2, 1, −3, 4, −1, 2, 1, −5, 4}</code>, the contiguous sub-array with the largest sum is <code>[4, −1, 2, 1]</code> with sum <code>6</code>.</em>" - From the Wiki Page.</p>
  </blockquote>
  
  <p>I am done with Kadane's and BruteForce, Where my required output is not just to find the sum, but also the <strong>starting index</strong> of the found sub-array and the <strong>ending index</strong>.</p>
  
  <p>My current <code>DivideAndConquer</code> code gets me the correct sum. However, I can't see a way to keep track of my indexes since I implemented it recursively (of course). And I don't know if the only way is to use global variables in this case (I prefer not).. Can you help solve that? Or will I need to change the whole design?</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  int DivideAndConquer(int[], int);
  
  int main()
  {
      // Example 1
      //const int MyArraySize = 16;
      //int MyArray[MyArraySize] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; // answer: Index 7 -&gt; 10, sum = 43
  
      // Example 2
      const int MyArraySize = 8;
      int MyArray[MyArraySize] = { -2, -5, 6, -2, -3, 1, 5, -6 }; // answer: Index 2 -&gt; 6, sum = 7
  
      int FinalResult;
  
      FinalResult = DivideAndConquer(MyArray, MyArraySize);
      std::cout &lt;&lt; "Using Divide And Conquer: With O(nlogn) Sum = " &lt;&lt; FinalResult &lt;&lt; "\n\n";
  
      system("pause");
      return 0;
  }
  
  int DivideAndConquer(int* _myArray, int _myArraySize)
  {
      if (_myArraySize == 1)
          return _myArray[0];
  
      int middle = _myArraySize / 2;
      int Result_LeftPortion = DivideAndConquer(_myArray, middle);
      int Result_RightPortion = DivideAndConquer(_myArray + middle, _myArraySize - middle);
  
      int LeftSum = -9999;
      int RightSum = -9999;
      int TotalSum = 0;
  
      for (int i = middle; i &lt; _myArraySize; i++)
      {
          TotalSum += _myArray[i];
          RightSum = TotalSum &lt; RightSum ? RightSum : TotalSum;
      }
  
      TotalSum = 0;
  
      for (int i = middle - 1; i &gt;= 0; i--)
      {
          TotalSum += _myArray[i];
          LeftSum = TotalSum &lt; LeftSum ? LeftSum : TotalSum;
      }
  
      int PartialResult = LeftSum &lt; RightSum ? RightSum : LeftSum;
      int Result= (PartialResult &lt; LeftSum + RightSum ? LeftSum + RightSum : PartialResult);
  
      return Result;
  }
  </code></pre>