1. 题目描述

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

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

2. 解法一：三层搜索

这个解法使用了3层搜索，时间复杂度为O(n^3)。

第一层搜索：i遍历数组中所有数，作为子数组的起始点；

第二层搜索：j遍历i到数组最后一个数，作为子数组的终止点；

第三层搜索：k遍历i到j，求得当前子数组和curSum，与maxSum比较；

我们再用下图来展示上层搜索过程：

Center

#include<iostream>
using namespace std; 
int MaxSubSum(int *a, int num)
{
    int curSum=0; 
    int maxSum=a[0]; 
    for(int i=0; i<num; i++)
    {
        for(int j=i; j<num; j++)
        {
            for(int k=i; k<=j; k++)
            {
                curSum+=a[k]; 
            }
            if(curSum>maxSum)
                maxSum=curSum; 
            curSum=0; 
        }
    }
    return maxSum; 
}
int main()
{
    int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; 
    int num=8; 
    int maxSum=MaxSubSum(a, num); 
    cout<<maxSum<<endl; 
    return 0; 
}

3. 解法二：前顾后盼法

其实我们是需要遍历一次即可，在遍历的这一次中，我们可以同时完成curSum和maxSum的工作。思路如下：

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md

对第j+1个元素有两种选择：要么放入前面找到的子数组，要么做为新子数组的第一个元素；
如果currSum加上当前元素a[j]后不小于a[j]，则令currSum加上a[j]，否则currSum重新赋值，置为下一个元素，即currSum = a[j]。
同时，当currSum > maxSum，则更新maxSum = currSum，否则保持原值，不更新。

代码如下：

#include<iostream>
using namespace std; 
int MaxSubSum(int *a, int num)
{
    int curSum=0; 
    int maxSum=a[0]; 
    for(int i=0; i<num; i++)
    {
        curSum=(curSum+a[i]>a[i]) ? curSum+a[i] : a[i]; 
        maxSum=maxSum>curSum ? maxSum : curSum; 
    }
    return maxSum; 
}
int main()
{
    int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; 
    int num=8; 
    int maxSum=MaxSubSum(a, num); 
    cout<<maxSum<<endl; 
    return 0; 
}