设数组A = [-4, ...]，sum为连续子数组元素的和，max_sum为当前最大子数组元素之和。
- 当遍历到A[0]时，sum=-4，max_sum=-4；
- 当遍历到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；
- 当遍历到A[2]时，sum为正数，如果sum(A[1:2])为非负数则进一步增长最大子数组，为负则最大子数组长度无法延长。假设A[2] = -3，sum更新为-1，max_sum不变；
- 当遍历到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;
}
