Maximum subsequence sum problem

The problem we’d like to solve can be stated as:

Given a sequence of numbers, find the maximum sum of a contiguous subsequence of those numbers.

One obvious solution is that we can simply enumerate every possible subsequence and calculate their sum. This will take O(n^2) time.

There is a linear solution called Kadane`s algorithm. Following is the code:

int max_sub_sum(int arr[], int len) {
    int max_local = 0;
    int max_global = 0;
    for(int i = 0; i < len; i++) {
        max_local += arr[i];
        if(max_local < 0)
            max_local = 0;
        if(max_local > max_global)
            max_global = max_local;
    }
    return max_global;
}

Why does it work? If max_local becomes negative, it will not contribute to the next subsequence by adding the next element. Actually the next element itself would be larger than the sum of it and max_local, so we can simply restart summing from here.

Note that this algorithm only works when there is at least one positive integer in the array.

Some interviewers may ask this question with slight modification that the input array is a circular array. In this case, we can concatenate the input array with itself, and apply Kadane`s algorithm.