Monday, October 3, 2011

Find the maximum sum of sub array within an array.


int maxSum(int *arr, int size)
{
    if(arr == NULL)
        return 0;
   
    int sum = 0, maxSum = 0, maxNo = arr[0];
    for(int i=0; i<size; ++i)
    {
        maxNo = arr[i] > maxNo ? arr[i] : maxNo;   //if all elem of array are negative the maxNo is the max sum
        sum += arr[i];
        if(sum < 0)
            sum = 0;
        else
            maxSum = sum > maxSum ? sum : maxSum;
    }
    if(maxNo < 0)
        return maxNo;
    return maxSum;
}

No comments:

Post a Comment