学步园

问题：给定一个数组，求最大连续子数组和，并输出开始和结束坐标。例如{-1,2,3,-2,5,-7,4,8,-2,1}，最大连续子数组为{2,3,-2,5,-7,4,8}，最大和为13，从下标1开始，到下标7结束。

一种思路是用DP。我们用一个数组max[]来记录以该元素为结尾的最大和，比如max[i]表示以arr[i]为结尾的最大连续子数组和。用一个begin[i]记录max[i]所对应的起始坐标。

对于max[i]，max[i]= MAX{max[i-1] + arr[i], arr[i]}，即以arr[i]结尾的最大连续子数组和要么是arr[i]，要么是以arr[i-1]结尾的最大和max[i-1]加上arr[i]。

代码如下：

struct result{
    int max;
    int begin;
    int end;
    result(): max(0x80000000), begin(0), end(0) {}
};


result DP(int *arr, int n)
{
    int max[n];
    int begin[n];
    int i;
    for(i=0; i<n; ++i)
    {
        max[i] = arr[i];
    }
    for(i=1; i<n; ++i)
    {
        if((max[i-1]+ arr[i]) > arr[i])
        {
            max[i] = max[i-1]+ arr[i];
            begin[i] = begin[i-1];
        }
        else
        {
            max[i] = arr[i];
            begin[i] = i;
        }
    }
    result rst;
    rst.max = max[0];
    for(i=1; i<n; ++i)
    {
        if(max[i] > rst.max)
        {
            rst.max = max[i];
            rst.begin = begin[i];
            rst.end = i;
        }
    }
    return rst;
}

用DP做，需要额外的空间max[]和begin[]。下面介绍一种比较高效的做法。先看下代码：

result maxSubArray(int *arr, int n)
{
    bool allNegative = true;    //判断数组元素是否全是非正数
    int i;
    result rst;
    for(i=0; i<n; i++)
    {
        if(arr[i] > rst.max)
        {
            rst.max = arr[i];
            rst.begin = i;
            rst.end = i;
        }
        if(arr[i] > 0)
        {
            allNegative = false;
            break;
        }
    }
    if(allNegative)
    {
        return rst;
    }

    int curr = 0;
    rst.max = 0;
    rst.begin = 0;
    rst.end = 0;
    bool flag = false;
    int tempBegin = 0;
    for(i=0; i<n; i++)
    {
        curr += arr[i];
        if(flag && (curr > 0))
        {
            flag = false;
            tempBegin = i;
        }
        if(curr > rst.max)
        {
            rst.max = curr;
            rst.end = i;
            rst.begin = tempBegin;
        }
        if(curr <= 0)
        {
            curr = 0;
            flag = true;
        }
    }
    return rst;
}

max表示最大连续和。当curr<0时，那么我们就令标志flag=true，以便在下一次curr>0时重设后备起点tempBegin。当curr大于0时，就做如下操作：当curr大于max时，就max=curr，并让begin=tempBegin，否则继续下一步。

这种做法有个问题，就是当数组元素全为非正数时就没发这么做。所以我们必须先预处理下，如果数组元素全为非正数时，就取最大的那个元素为max。