int MaxSubArray(int A[], int n) 
{
    int sum = A[0];
    int cur = A[0];
    for (int i = 1; i < n; ++i)
    {
        if (cur <0)
            cur = A[i];
		else
			cur += A[i];

        if (sum < cur) sum = cur;
    }

    return sum;
}



#include <stdio.h>

int main(int argc, char** argv)
{
    int a[]={-2,1,-3,4,-1,2,1,-5,4};
    int n = sizeof(a) / sizeof(int);

    printf("%d\n", MaxSubArray(a,n));
    return 0;
}