Maximum Sum Sub-array (Kadane's Algorithm)

Question: Given an array of integers (both positive and negative), find the sub-array with maximum sum. Example: An array -3, 2, -4, 4, -1, 3, 2, -5, 4 should return the sum as eight, sub-array start index is 3 and sub-array end index is 6.


Time Complexity: O(n)


int
maximum_sum_subarray(int *array, int length, int *max_sum, int *max_start, int *max_end)
{
    int cur_sum = 0, cur_start = 0, cur_end = 0;


    for (cur_end = 0; cur_end < length; cur_end++) {
        cur_sum += array[cur_end];
        if (cur_sum > *max_sum) {
            *max_sum = cur_sum;
            *max_start = cur_start;
            *max_end = cur_end;
        }


        if (cur_sum < 0) {
            cur_sum = 0;
            cur_start = cur_end + 1;
        }
    }
}