求连续子数组的最大和

题目来源：《剑指offer》面试题31，《编程珠玑》第八章，LeetCode OJ的Maximum Subarray。

题目大意：

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的最大和。

例如，数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此返回的结果为子数组的和18.

来自Google，微软等很多知名公司的面试题，2005年浙江大学计算机系的考研题的最后一道程序设计题，貌似是风靡一时的一道题。

参考链接：程序员编程艺术：第七章、求连续子数组的最大和、程序员面试题精选100题(03)－子数组的最大和

解题思路：

解法一：O(n3)

最最简单粗暴的解法，就是列出数组的所有子集，然后一一计算总和，记录最大值。

不多说，伪代码就是这样：

maxsofar = 0;
for i = [0,n)
    for j = [i,n)
        sum = 0;
        for k = [i,j]
            sum += x[k];
            //sum is sum of x[i...j]
            maxsofar = max(maxsofar,sum);

View Code

解法二：O(n2)

基本上就是在解法一的基础上，把最里面的那层循环消去。

因为x[i...j]的总和与前面已计算出的总和（x[i...j-1]的总和）密切相关。

maxsofar = 0;
for i = [0,n)
    sum = 0;
    for j = [i,n)
        sum += x[j];
        //sum is sum of x[i...j]
        maxsofar = max(maxsofar,sum);

View Code

解法三：O(nlogn)

分治算法。

要解决规模为n的问题，可以递归的解决两个规模近似为n/2的子问题，然后对他们的答案进行合并以得到整个问题的答案。

若m为中间的数，a为左边的集合，b为右边的集合，那么最大子集和要么在a中，要么在b中，要么横跨a和b包括了a的右边和b的左边。

代码就这个：

//动态规划
int max_3(int a,int b,int c){
    if(a >= b){
        return a>=c?a:c;
    }
    else{
        return b>=c?b:c;
    }
            
}
int maxsum3(int *x,int l,int u){
    if(l > u)
        return 0;
    if(l == u)
        return x[l]>=0? x[l]:0;
    int m = (l+u)/2;

    int lmax,sum,rmax;
    lmax = sum = 0;
    for(int i = m; i >= l; i--){
        sum += x[i];
        if(sum > lmax)
            lmax = sum;
    }

    rmax = sum = 0;
    for(int i = m;i <= u; i++){
        sum += x[i];
        if(sum > rmax)
            rmax = sum;
    }
    int lr = lmax+rmax;
    int ll = maxsum3(x,l,m);
    int rr = maxsum3(x,m+1,u);

    return max_3(lr,ll,rr);
}

View Code

解法四：O(n)

扫描算法。（动态规划）

设置两个辅助变量，curSum和greatestSum（在编程珠玑中为maxendinghere和maxsofar）。
为了区别传入指针为空指针时返回0和正常计算最大值返回0的情况，我们需要添加一个全局变量invalidInput来标志。
一个for循环遍历数组，i 表示当前下标，如果curSum < 0，我们就让curSum = pData[i]，否则就让curSum += pData[i]，因为当curSum小于0的时候，再加上pData[i]的结果必然比 pData[i] 小，不如将curSum清0，只包含pData[i] 一个元素。
然后再用greatestSum每次跟curSum比较，记录下当前的最大值。

《编程珠玑》的伪代码：

maxsofar = 0;
maxendinghere = 0;
for i = [0,n)
    maxendinghere = max(maxendinghere + x[i], 0);
    maxsofar = max(maxsofar,maxendinghere);

《剑指offer》的代码：

bool invalidInput = false;
int FindGreatestSumOfSubArray(int *pData,int nLength){
    if((pData == NULL) || nLength <= 0){
        invalidInput = true;
        return 0;
    }
    invalidInput = false;

    int curSum = 0;
    int greatestSum = 0x80000000;//-2147483648
    for(int i = 0; i < nLength; i++){
        if(curSum < 0)
            curSum = pData[i];
        else
            curSum += pData[i];
        if(curSum > greatestSum)
            greatestSum = curSum;
    }
    return greatestSum;
}

主函数：

int main(){
    int a[] = {1,-2,3,10,-4,7,2,-5};
    int sum = FindGreatestSumOfSubArray(a,sizeof(a)/sizeof(int));
    //int sum = MaxSum(a,sizeof(a)/sizeof(int));
    //int sum = maxsum3(a,0,14);
    cout << sum << endl;
    getchar();
    return 0;    
}

View Code