Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum = 6.

S[0] = 0;for (i = 1; i <= n; i++)  S[i] = S[i-1] + A[i];for (i = 1; i <= n; i++)      for (j = i; j <= n; j++)           best = max(best, S[j] - S[i-1]);

int maxSubArray(int* nums, int numsSize) {    int *S;    S = (int*)malloc((numsSize+5) * sizeof(int) );    int i,j;    int best = nums[0];    S[0] = 0;        for (i=1; i<=numsSize; i++) {        S[i] = S[i-1] + nums[i-1];    }    for (i=1; i<=numsSize; i++) {        for (j=i; j<=numsSize; j++) {            best = best > (S[j]-S[i-1]) ? best : (S[j]-S[i-1]);        }    }    free(S);    return best;}