The maximum subarray problem is to find the subarray within an array of integers with the largest sum. There is a linear time dynamic programming algorithm for solving it invented by Joseph Kadane.

Here it is in C:

int max(int a, int b)
{
    return a > b ? a : b;
}

int max_subarray(int *array, size_t n)
{
    int max_ending_here = 0;
    int max_so_far = 0;
    unsigned int i;

    for (i = 0; i < n; i++) {
        max_ending_here = max(0, max_ending_here + array[i]);
        max_so_far = max(max_so_far, max_ending_here);
    }
    return max_so_far;
}

Example program:

int main(void)
{
    int array[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    const size_t n = sizeof(array) / sizeof(int);
    printf("Max subarray sum is %d\n", max_subarray(array, n));
    return 0;
}

Output:

6