title: Maximum sub array using D&C/Recursion
body: <p>I want to implement Maximum Sub Array problem with an algorithm that exhibits (n log n):</p>
  
  <p>Find the maximum contigous sub array, or maximum sum of contiguous elements in the array.</p>
  
  <p>Assumption:not all elements are negative numbers</p>
  
  <hr>
  
  <p>I have somewhat working solution; the problem is with the overlapping center array, and the appropriate indexes that designate overlapping sub problems, some arrays Im getting the right answer on other not. </p>
  
  <hr>
  
  <p>Just for comparison &amp; for cheking correctness I implemented a solution known as Kadane’s algorithm 
  (I believe the complexity is Omega(n)).</p>
  
  <p>This is Kandane’s algorithm(http://en.wikipedia.org/wiki/Maximum_subarray_problem):</p>
  
  <hr>
  
  <pre><code> public static void Kadane(int array[]) {
          int max_ending_here = 0;
          for (int i = 0; i &lt; array.length; i++) {
              max_ending_here = max_ending_here + array[i];
              max_so_far = Math.max(max_so_far, max_ending_here);
          }
          System.out.println("Kadane(int array []): " + max_so_far);
      }
  </code></pre>
  
  <hr>
  
  <p>My recursive implementation, that uses divide &amp; conquer to compare sub array's max's , then make's recursive call on the sub array that has the max, until the recursion ends</p>
  
  <pre><code>public static void findMaxSubArray(int[] array, int lowIndex, int highIndex) {
  
          int mid = 0;
          int arrayLength = 0;
          int maxEndingHere = 0;
  
          if (array == null) {
              throw new NullPointerException();
          } else if 
                  //base condition 
             (array.length &lt; 2 || (highIndex==lowIndex)) {
              maxLowIndex = lowIndex;
              maxHighIndex = highIndex;
              System.out.println("findMaxSubArray(int[] array, int lowIndex, int highIndex)");
              System.out.println("global Max Range, low:" + maxLowIndex + " high: " + maxHighIndex);
              System.out.println("global Max Sum:" + globalMaximum);
          } else {
              System.out.println();
              int lowMidMax = 0;
              int midHighMax = 0;
              int centerMax = 0;
              //array length is always the highest index +1 
              arrayLength = highIndex + 1;
  
              //if even number of elements in array 
              if (array.length % 2 == 0) {
                  mid = arrayLength / 2;
                  System.out.println("low: " + lowIndex + " mid: " + mid);
                  for (int i = lowIndex; i &lt; mid; i++) {
                      System.out.print(array[i] + ",");
                  }
                  //calculate maximum contigous array encountered so far in low to mid indexes 
                  for (int i = lowIndex; i &lt; mid; i++) {
                      maxEndingHere = maxEndingHere + array[i];
                      if (maxEndingHere &lt; 0) {
                          maxEndingHere = 0;
                      }
  
                      if (globalMaximum &lt; maxEndingHere) {
                          //new maximum found 
                          globalMaximum = lowMidMax = maxEndingHere;
                          lowIndex = i;
                      }
  
                  }
                  //end low mid calc 
  
                  for (int i = mid; i &lt;= highIndex; i++) {
                      System.out.print(array[i] + ",");
                  }
                  System.out.println("mid: " + mid + " high: " + highIndex);
                  //calculate maximum contigous array encountered so far in mid to high indexes 
                  for (int i = mid; i &lt;= highIndex; i++) {
                      maxEndingHere = maxEndingHere + array[i];
                      if (maxEndingHere &lt; 0) {
                          maxEndingHere = 0;
                      }
  
                      if (globalMaximum &lt; maxEndingHere) {
                          //new maximum found 
                          globalMaximum = midHighMax = maxEndingHere;
                          mid = i;
                      }
  
                  }
  //end mid high calc
                  //calculate maximum contigous array encountered so far in center array
                  int lowCenter = mid -1;
                  int highCenter = highIndex -1;
  
                  System.out.println("lowCenter: " + lowCenter + " highCenter: " + highCenter);
                  for (int i = lowCenter; i &lt; highCenter; i++) {
                      System.out.print(array[i] + ",");
                  }
                  //calculate maximum contigous array encountered so far in low to mid indexes 
                  for (int i = lowCenter; i &lt; highCenter; i++) {
                      maxEndingHere = maxEndingHere + array[i];
                      if (maxEndingHere &lt; 0) {
                          maxEndingHere = 0;
                      }
  
                      if (globalMaximum &lt; maxEndingHere) {
                          //new max found
                          globalMaximum = centerMax = maxEndingHere;
                          lowCenter = i;
  
                      }
  
                  }
                  //end center calc 
                  //determine which range contains the maximum sub array 
                  //if lowMidMax &lt;= midHighMax and centerMax
                  if (lowMidMax &gt;= midHighMax &amp;&amp; lowMidMax &gt;= centerMax) {
                      maxLowIndex = lowIndex;
                      maxHighIndex = mid;
                      //recursive call
                      findMaxSubArray(array, lowIndex, mid);
                  }
                  if (midHighMax &gt;= lowMidMax &amp;&amp; midHighMax &gt;= centerMax) {
                      maxLowIndex = mid;
                      maxHighIndex = highIndex;
                      //recursive call
                      findMaxSubArray(array, mid, highIndex);
                  }
                  if (centerMax &gt;= midHighMax &amp;&amp; centerMax &gt;= lowMidMax) {
                      maxLowIndex = lowCenter;
                      maxHighIndex = highCenter;
                      //recursive call
                      findMaxSubArray(array, lowCenter, highCenter);
                  }
  
              }//end if even parent array 
              //else if uneven array 
              else {
                  mid = (int) Math.floor(arrayLength / 2);
                  System.out.println("low: " + lowIndex + " mid: " + mid);
                  for (int i = lowIndex; i &lt; mid; i++) {
                      System.out.print(array[i] + ",");
                  }
                  //calculate maximum contigous array encountered so far in low to mid indexes 
                  for (int i = lowIndex; i &lt; mid; i++) {
                      maxEndingHere = maxEndingHere + array[i];
                      if (maxEndingHere &lt; 0) {
                          maxEndingHere = 0;
                      }
  
                      if (globalMaximum &lt; maxEndingHere) {
                          //new maximum found 
                          globalMaximum = lowMidMax = maxEndingHere;
                          lowIndex = i;
                      }
  
                  }
                  //end low mid calc
                  System.out.println("mid+1: " + (mid + 1) + " high: " + highIndex);
                  for (int i = mid + 1; i &lt;= highIndex; i++) {
                      System.out.print(array[i] + ",");
                  }
                  //calculate maximum contigous array encountered so far in mid to high indexes 
                  for (int i = mid + 1; i &lt;= highIndex; i++) {
                      maxEndingHere = maxEndingHere + array[i];
                      if (maxEndingHere &lt; 0) {
                          maxEndingHere = 0;
                      }
  
                      if (globalMaximum &lt; maxEndingHere) {
                          //new maximum found 
                          globalMaximum = midHighMax = maxEndingHere;
                          mid = i;
                      }
  
                  }
                  //end mid high calc
                  //calculate maximum contigous array encountered so far in center array
                  int lowCenter =  mid;
                  int highCenter = highIndex -1;
  
                  System.out.println("lowCenter: " + lowCenter + " highCenter: " + highCenter);
                  for (int i = lowCenter; i &lt; highCenter; i++) {
                      System.out.print(array[i] + ",");
                  }
                  //calculate maximum contigous array encountered so far in low to mid indexes 
                  for (int i = lowCenter; i &lt; highCenter; i++) {
                      maxEndingHere = maxEndingHere + array[i];
                      if (maxEndingHere &lt; 0) {
                          maxEndingHere = 0;
                      }
  
                      if (globalMaximum &lt; maxEndingHere) {
                          //new max
                          globalMaximum = centerMax = maxEndingHere;
                          lowCenter = i;
                      }
  
                  }
                  //end center calc 
  
                  //determine which range contains the maximum sub array 
                  //if lowMidMax &lt;= midHighMax and centerMax
                    if (lowMidMax &gt;= midHighMax &amp;&amp; lowMidMax &gt;= centerMax) {
                      maxLowIndex = lowIndex;
                      maxHighIndex = mid;
                      //recursive call
                      findMaxSubArray(array, lowIndex, mid);
                  }
                  if (midHighMax &gt;= lowMidMax &amp;&amp; midHighMax &gt;= centerMax) {
                      maxLowIndex = mid;
                      maxHighIndex = highIndex;
                      //recursive call
                      findMaxSubArray(array, mid, highIndex);
                  }
                  if (centerMax &gt;= midHighMax &amp;&amp; centerMax &gt;= lowMidMax) {
                      maxLowIndex = lowCenter;
                      maxHighIndex = highCenter;
                      //recursive call
                      findMaxSubArray(array, lowCenter, highCenter);
                  }
  
  
              }//end odd parent array length 
          }//end outer else array is ok to computed 
  
      }//end method
  </code></pre>
  
  <hr>
  
  <p>Results : using array subArrayProblem1 = {1, 2, 3, 4, 5, 6, 7, 8};</p>
  
  <p><strong>Kadane(int array []): 36</strong>
  low: 0 mid: 4
  1,2,3,4,5,6,7,8,mid: 4 high: 7
  lowCenter: 6 highCenter: 6</p>
  
  <p>findMaxSubArray(int[] array, int lowIndex, int highIndex)
  global Max Range, low:7 high: 7
  <strong>global Max Sum:36</strong>
  BUILD SUCCESSFUL (total time: 0 seconds)</p>
  
  <p>Issues although the global max sum is correct when compared to Kadane, the low index &amp; high index range reflects the last recusive call. </p>
  
  <p>Results : using array subArrayProblem = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};</p>
  
  <p>Kadane(int array []): 1607
  low: 0 mid: 8
  100,113,110,85,105,102,86,63,mid+1: 9 high: 16
  101,94,106,101,79,94,90,97,lowCenter: 16 highCenter: 15</p>
  
  <p>findMaxSubArray(int[] array, int lowIndex, int highIndex)
  global Max Range, low:16 high: 16
  global Max Sum:1526</p>
  
  <p>The global max is not correct, note the difference is actually 1 element , which is the element 81</p>