Write an algorithm and C code to find the sub array with the largest sum given an array that contains both positive and negative integers

The information to be kept while going through the array only once (O(n)) is the best sub array
ending in the current position and best sub array found for the entire array until the current step. If
necessary, the starting and ending position for the sub array can be kept. After the processing of the
last element, the algorithm will have determined the sub array having the largest sum. The algorithm
works fine even if there is no negative number in the array.
Algorithm: “arr” is the array of n integer. The function will return the largest sum and the limits of
the sub array producing that value.
int GetBestSubArray(int* arr , int n , int* nBegin , int* nEnd)
{
//starting/ending position of the best sub array for entire array
int nBestBegin=0,nBestEnd=0;
//starting/ending position of the best sub array ending in
//current position
int nCrtBegin=0,nCrtEnd=0;
// index to loop in the array
int nCrtIndex = 0;
//the sum of whole best sub array and the sum of current best
//sub array
int nBestSum=0, nCrtSum=0;
//Nothing to analyze, return invalid array indexes
if (n == 0){
(*nEnd)=(*nBegin)=-1;
return 0;
}
nBestSum=nCrtSum = arr[nCrtIndex];
for(nCrtIndex=1;nCrtIndex//Compute the current largest sum
if (nCrtSum<0 br="">nCrtSum = arr[nCrtIndex];
nCrtEnd = nCrtBegin=nCrtIndex;
}
else {
nCrtSum+= arr[nCrtIndex];
nCrtEnd=nCrtIndex;
}
if (nCrtSum > nBestSum) {
nBestSum = nCrtSum;
nBestBegin=nCrtBegin;
nBestEnd=nCrtEnd;
}
}
*nBegin=nBestBegin;
*nEnd=nBestEnd;
return nBestSum;
}
//Sample driver
int main ()
{
int arr[5] = { 1, 5, 6, -1, -2 };
int nBegin =0;
int nEnd = 0;
int nBestSum = GetBestSubArray(arr, 5, &nBegin, &nEnd);
cout << "Sum=" << nBestSum << "Begin Index=" << nBegin
<< "End Index=" <return 1;
}