『C语言学习笔记』最大子数组的线性时间算法

设数组A = [-4, ...]，sum为连续子数组元素的和，max_sum为当前最大子数组元素之和。

1. 当遍历到A[0]时，sum=-4，max_sum=-4；
2. 当遍历到A[1]时，无论元素值是多少，最大子数组不可能是A[0:1]，因为A[0]是负数，sum(A[0:1]) < A[1]是必然的。所以遍历到A[i]时，如果sum是负数，则sum=A[i]。假设A[1] = 2，sum更新为2，max_sum更新为2；
3. 当遍历到A[2]时，sum为正数，如果sum(A[1:2])为非负数则进一步增长最大子数组，为负则最大子数组长度无法延长。假设A[2] = -3，sum更新为-1，max_sum不变；
4. 当遍历到A[3]时，sum为负数，此时同遍历A[1]时的情况一样。

typedef struct 
{
    int sum, start, end;
} Ans;

Ans* max_subarray(int* array, int length)
{
    int sum = -1, max_sum = INT_MIN, i, low, high, cur_low;

    for (i = 0; i < length; i++)
    {
        if (sum >= 0) 
            sum += array[i];
        else
        {
            sum = array[i];
            cur_low = i;
        }

        if (sum > max_sum)
        {
            max_sum = sum;
            low = cur_low;
            high = i;
        }
    }

    Ans* ans = malloc(sizeof(Ans));
    ans->sum = sum;
    ans->start = low;
    ans->end = high;
    return ans;
}