面试题31：连续子数组的最大和

题目：输入一个整型数组，数组中有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要为时间复杂度为O(n)。

分析

可以这么想，假设这个数组的具有最大和的连续子数组区间为[x,y)，该数组的中间元素的下标是mid。mid和[x,y)的关系又一下三种：

• mid<x
• mid>=y
• x<=mid<y

所以，对于前两种情况，由于mid并不包含在最大子数组里，所以可使left=x或right=y，然后递归求解。

对于第三种情况，可从mid分别向左和右遍历，找出边界下标。

代码如下：

int _FindMaxCrossSumArray(vector<int> v,int left,int mid,int right)
{
    int LeftSum=-2147483647,RightSum=-2147483647;
    int LeftPos,RightPos;
    int Sum=0;
    int i;
    for(i=mid;i>=left;--i)
    {
        Sum+=v[i];
        if(Sum>LeftSum)
        {
            LeftSum=Sum;
            LeftPos=i;
        }
    }
    Sum=0;
    for(i=mid+1;i<=right;++i)
    {
        Sum+=v[i];
        if(Sum>RightSum)
        {
            RightSum=Sum;
            RightPos=i;
        }
    }
    Sum=0;
    for(i=LeftPos;i<=RightPos;++i)
    {
        Sum+=v[i];
    }
    return Sum;
}

int _FindGreatestSumOfSubArray(vector<int> v,int left,int right)
{
    if(left>=right)
        return v[left];
    int mid=left+(right-left)/2;
    int LeftSum=_FindGreatestSumOfSubArray(v,left,mid);
    int RightSum=_FindGreatestSumOfSubArray(v,mid+1,right);
    int MidSum=_FindMaxCrossSumArray(v,left,mid,right);
    if(LeftSum>=RightSum &amp;&amp; LeftSum>=MidSum)
        return LeftSum;
    else if(RightSum>=LeftSum &amp;&amp; RightSum>=MidSum)
        return RightSum;
    else
        return MidSum;
}

int FindGreatestSumOfSubArray(vector<int> v)
{
    if(v.size()<=0)
        throw new exception();
    return _FindGreatestSumOfSubArray(v,0,v.size()-1);
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往