求解和最大的子串

对于一个存在正负数的整型数组,在时间复杂度为O(n)内,求解和最大的子串和.

例如:

a[10] = {3,-300,4,5,0,-8,9,-9,10,-100}

最大字串: a[2]~a[8], 和: 11

解法:

int max_sub(int* p, int size, int* start, int* end)
{
    int i = 0;
    int temp_sum,ret;
    int count = 0;

    temp_sum= ret = 0;

    for(i = 0; i < size; i++)
    {
        temp_sum += p[i];
        if(ret < temp_sum)
        {
            ret = temp_sum;
            if(count == 0)
            {
                *start = i;
                count++;
                continue;
            }

            if(count == 1)
            {
                *end = i;
            }
        }
        else if(temp_sum < 0)
        {   
            count = 0;
            temp_sum = 0;
        }
    }
    return ret;
}