No. 03 - Maximum Sum of All Sub-arrays - solution

findMaximumSumOfSubArray.cpp

//http://codercareer.blogspot.kr/2011/09/no-03-maximum-sum-of-all-sub-arrays.html
#include <stdio.h>
#include <algorithm>
#include <assert.h>

using namespace std;

int findMaximumSumOfSubArray(int *array, int length) {
  if (array == NULL || length <= 0) {
    printf("wrong input \n");
    return 0;
  }

  int currentSum = 0;
  int maximumSum = 0;

  for (int i = 0; i < length; i++) {
    currentSum = max(currentSum + array[i], array[i]);

    if (currentSum > maximumSum) {
      maximumSum = currentSum;
    }
  }

  return maximumSum;
}

int main(void) {
  int array1[5] = {-2, -4, 5, -1, 0};
  int array2[5] = {1, 4, 6, 2, 5};
  int array3[5] = {-1, 5, 2, -6, 10};
  int array4[5] = {-10, 1, -9, -1, 2};

  assert(findMaximumSumOfSubArray(array1, 5) == 5);
  assert(findMaximumSumOfSubArray(array2, 5) == 18);
  assert(findMaximumSumOfSubArray(array3, 5) == 11);
  assert(findMaximumSumOfSubArray(array4, 5) == 2);

  return 0;
}