连续子数组和的最大值

Q：定义：数组中连续一个或多个元素组成一个连续子数组。一个整型数组，求其所有连续子数组的和的最大值，要求O(n)。

本题为2005年浙大计算机系考研题的一个程序设计题。

分析： 最简单的方法就是求出所有的连续子数组，然后求其最大值。n个元素的整数数组为 1 + 2 +...+ n = n(n+1)/2, 这一步的时间复杂度为O(n²), 显然不满足O(n)要求。
再看题目：求连续子数组的和的最大值。求和的最大值，当加个正数时，和会增加；当加一个负数时，和会减少。当当前和的值为负数时，应该把当前和清零。

代码：

/* this algrithm suppose the int is not overflow */
int get_max_seq_sub_arr_sum(int arr[], int size) {
    int max_sum = 0, cur_sum = 0, i;

    if(arr == NULL || size < 0) {
        exit(1);
    }

    for(i = 0; i < size; i++) {
        cur_sum += arr[i];
        if(cur_sum < 0)
            cur_sum = 0;

        if(cur_sum > max_sum)
            max_sum = cur_sum;
    }

    if(max_sum == 0) { /* all elements in array are not positive */
        max_sum = arr[0];
        for(i = 1; i < size; i++) {
            if(max_sum < arr[i])
                max_sum = arr[i];
        }
    }

    return max_sum;
}