#include <iostream>

using namespace std;

//we can also put the sum as a parameter
int getMaxSubSum(int *nArray, int n) {

  if(nArray==NULL || n<1)
    return -1;

  int maxSum = 0;
  int currentSum = 0;

  int begin = 0;
  int end = 0;

  for(int i=0; i<n; i++) {
    currentSum += nArray[i];

    if(currentSum<0) {
      currentSum=0;
      begin = i+1;
    }

    if(maxSum<currentSum) {
      maxSum = currentSum;
      end = i; //
    }
  }

  if(maxSum==0) {
    maxSum = nArray[0];
    for(int i=1;i<n;i++) {
      if(maxSum<nArray[i])
	maxSum = nArray[i];
    }
  }


  //print out the sub array
  for(int i=begin; i<=end; i++) {
    cout << nArray[i] << " ";
  }
  cout << endl;

  return maxSum;

}

int main(int argc, char **argv) {
  int array[] = {1, -2, 3, 10, -4};

  int result = getMaxSubSum(array, 5);
  cout << "Max Sum: " << result << endl;

  return 0;
}