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

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

看到这个题目，我们首先想到的是求出这个整型数组所有连续子数组的和，长度为n的数组一共有 n(n+2)/2个子数组，因此要求出这些连续子数组的和最快也需要O(n^2)的时间复杂度。但是题目要求的O(n)的时间复杂度，因此上述思路不能解决问题。

看到O(n)时间复杂度，我们就应该能够想到我们只能对整个数组进行一次扫描，在扫描过程中求出最大连续子序列和以及子序列的起点和终点位置。假如输入数组为{1,-2,3,10,-4,7,2,-5}，我们尝试从头到尾累加其中的正数，初始化和为0，第一步加上1，此时和为1，第二步加上-2，此时和为-1，第三步加上3，此时我们发现-1+3=2，最大和2反而比3一个单独的整数小，这是因为3加上了一个负数，发现这个规律以后我们就重新作出累加条件：如果当前和为负数，那么就放弃前面的累加和，从数组中的下一个数再开始计数。

代码实例：

View Code

#include<iostream>
#include<stdlib.h>
using namespace std;

//求最大连续子序列和
int FindGreatestSumOfSubArray(int arry[],int len)
{
    if(arry==NULL||len<=0)
        return -1;
    int start=0,end=0;//用于存储最大子序列的起点和终点
    int currSum=0;//保存当前最大和
    int greatestSum=-10000;//保存全局最大和
    for(int i=0;i<len;i++)
    {
        if(currSum<0)//如果当前最大和为负数，则舍弃前面的负数最大和，从下一个数开始计算
        {
            currSum=arry[i];
            start=i;
        }
        else
            currSum+=arry[i];//如果当前最大和不为负数则加上当前数
        if(currSum>greatestSum)//如果当前最大和大于全局最大和，则修改全局最大和
        {
            greatestSum=currSum;
            end=i;
        }
    }
    cout<<"最大子序列位置:"<<start<<"--"<<end<<endl;
    return greatestSum;
}



void main()
{
    int arry[]={1,-2,3,10,-4,7,2,-5};
    int len=sizeof(arry)/sizeof(int);
    //cout<<len<<endl;
    int sum= FindGreatestSumOfSubArray(arry,len);
    cout<<"最大子序列和："<<sum<<endl;

    system("pause");
}

更正连续子序列位置错误的问题（PS:2012-8-10）

经过@Yu's 技术生涯测试，发现我上面的代码确实存在问题，现在做了如下修改：

1.添加了一个遍历用于保存遍历数组中发现的最大和的起始，原来的start和end只用于保存真是的开始于结尾。
2.当currSum<0的时候，我们只让p值为最大和子数组的开始
3.在最后判断currSum>greatestSum的时候，只有当currSum>greatestSum成立，才让start=p，否则就表明以p开头的子数组最大和不是最大的。

示例代码如下：

View Code

#include<iostream>
#include<stdlib.h>
using namespace std;

//求最大连续子序列和
int FindGreatestSumOfSubArray(int arry[],int len)
{
    if(arry==NULL||len<=0)
        return -1;
    int start=0,end=0;//用于存储最大子序列的起点和终点
    int p=0;//指针，用于遍历数组。
    int currSum=0;//保存当前最大和
    int greatestSum=-10000;//保存全局最大和
    for(int i=0;i<len;i++)
    {
        if(currSum<0)//如果当前最大和为负数，则舍弃前面的负数最大和，从下一个数开始计算
        {
            currSum=arry[i];
            p=i;
        }
        else
            currSum+=arry[i];//如果当前最大和不为负数则加上当前数
        if(currSum>greatestSum)//如果当前最大和大于全局最大和，则修改全局最大和
        { 
            greatestSum=currSum;
            start=p;
            end=i;
        }
    }
    cout<<"最大子序列位置:"<<start<<"--"<<end<<endl;
    return greatestSum;
}



void main()
{
    //int arry[]={1,-2,3,10,-4,7,2,-5};
    int arry[]={1,-2,3,10,-4,7,2,-19,2};
    int len=sizeof(arry)/sizeof(int);
    //cout<<len<<endl;
    int sum= FindGreatestSumOfSubArray(arry,len);
    cout<<"最大子序列和："<<sum<<endl;

    system("pause");
}

使用动态规划方法（PS：2012-10-9）

解体思路：

如果用函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max(f[0...n])。我们可以给出如下递归公式求f(i)

这个公式的意义：

当以第(i-1)个数字为结尾的子数组中所有数字的和f(i-1)小于0时，如果把这个负数和第i个数相加，得到的结果反而不第i个数本身还要小，所以这种情况下最大子数组和是第i个数本身。
如果以第(i-1)个数字为结尾的子数组中所有数字的和f(i-1)大于0，与第i个数累加就得到了以第i个数结尾的子数组中所有数字的和。

代码实现

View Code

//使用动态规划求最大连续子数组和
int FindGreatestSumOfSubArray2(int arry[],int len,int c[])
{
    c[0]=arry[0];
    int start,end;
    int temp=0;
    int maxGreatSum=-100;
    for(int i=1;i<len;i++)
    {
        if(c[i-1]<=0)
        {
            c[i]=arry[i];
            temp=i;
        }
        else
            c[i]=arry[i]+c[i-1];
        if(c[i]>maxGreatSum)
        {
            maxGreatSum=c[i];
            start=temp;
            end=i;
        }
    }
    //输出c[i]
    for(int i=0;i<len;i++)
        cout<<c[i]<<" ";
    cout<<endl;

    cout<<"最大子序列位置:"<<start<<"--"<<end<<endl;
    return maxGreatSum;
}

其实上述两种方法的实现方式非常相似，只是解体思路不同而已。通常我们会使用递归的方式分析动态规划的问题，但是最终都会基于循环去写代码。在动态规划方法中创建了一个数组c[]用于存储中间结果，而第一种方法中只需要一个临时变量currSum.