53. Maximum Subarray

Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Approach : Kadene's Algorithm

def max_subarray(A):
max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Source: Wikipedia

Solution:

int maxSubArray(int* nums, int numsSize) {
    int curSum, maxSum = INT_MIN;
    curSum = 0;
    for(int i = 0; i < numsSize; i++){
        curSum = curSum + nums[i];
        if(curSum > maxSum){
            maxSum = curSum;
        }
        if(curSum < 0){
            curSum = 0;
        }
    }
    return maxSum;
}

Here is the link to the ideone solution : http://ideone.com/howey4