#include <math.h>
#include <stdio.h>

int maxSum(int sequence[], int lowestIndex, int highestIndex) {
  
  if (lowestIndex == highestIndex) {
    //This is the base case.
    if (sequence[lowestIndex] > 0) {
      return sequence[lowestIndex];
    } else {
      return 0;
    }
  }

  int centerIndex = (lowestIndex + highestIndex) / 2; //Divide the sequence inte two halves.

  //Find the biggest sum that starts in one half and ends in the other ("case three").
  int biggestSumInLeftSequence = 0;
  int sum = 0;
  for (int i=centerIndex; i>=lowestIndex; i--) {
    sum += sequence[i];
    if (sum > biggestSumInLeftSequence) {
      biggestSumInLeftSequence = sum;
    }
  }
  int biggestSumInRightSequence = 0;
  sum = 0;
  for (int i=centerIndex+1; i<=highestIndex; i++) {
    sum += sequence[i];
    if (sum > biggestSumInRightSequence) {
      biggestSumInRightSequence = sum;
    }
  }

  int maxInBoth = (biggestSumInLeftSequence + biggestSumInRightSequence);

  //Find the biggest sums in the two halves of the sequence ("case one and two").
  int maxInLeftHalf  = maxSum(sequence, lowestIndex, centerIndex);
  int maxInRightHalf = maxSum(sequence, centerIndex+1, highestIndex);
  
  // Return the biggest of the three sums calculated above.
  int biggest = 0;
  if (maxInLeftHalf > maxInRightHalf) {
    biggest = maxInLeftHalf;
  } else {
    biggest = maxInRightHalf;
  }
  
  if (biggest > maxInBoth) {
    return biggest;
  } else {
    return maxInBoth;
  }

}

main() {
  int theSequence[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};

  printf("the maximum sum is: %d\n", maxSum(theSequence, 0, 9));
}