最大连续子数组和

题目描述：

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

分析和解法：

解法一：暴力求解

我们可以找出所有连续子数组，并求解它们的和，找出最大值。
源代码如下：

#include <iostream>
#include <limits>

using namespace std;

int main()
{
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[n++];
    int maxsum = INT_MIN;
    int currsum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            for (int k = i; k <= j; k++)
                currsum += a[k];
            if (currsum > maxsum)
                maxsum = currsum;
            currsum = 0;  ////这里要记得清零，否则的话 currsum 最终存放的是所有子数组的和
        }
    }
    cout << maxsum << endl;
    return 0;   
}

分析：时间复杂度为 O（n ^ 3）。

解法二：顺序扫描

这种解法是按顺序一个一个的加到 currsum 中，如果 currsum < 0 ，那么 currsum 置为下一个元素，然后持续比较 maxsum 和 currsum 的大小，使得 maxsum 为最大值。
源代码如下：

#include <iostream>
#include <limits>

using namespace std;

int main()
{
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[n++];
    int maxsum = INT_MIN;
    int currsum = 0;
    for (int i = 0; i < n; i++)
    {
        if (currsum < 0)
            currsum = a[i];
        else 
            currsum += a[i];
        if (currsum > maxsum)
            maxsum = currsum;       
    }
    cout << maxsum << endl;
    return 0;   
}

分析：时间复杂度为 O（n）。

解法三：动态规划

这是一个很经典的动态规划问题。
令 currsum 为当前最大子数组的和，maxsum 为最后要返回的最大子数组的和。对第 j+1 个元素有两种选择：要么放入前面找到的子数组，要么作为新子数组的第一个元素。

currsum = max(a[j], currsum + a[j])
maxsum = max(maxsum, currsum)

源代码如下：

#include <iostream>
#include <limits>

using namespace std;

int main()
{
    int a[100];
    int n = 0;
    while(cin.peek() != '\n')  cin >> a[n++];
    int maxsum = INT_MIN;
    int currsum = 0;
    for (int i = 0; i < n; i++)
    {
        currsum = (currsum + a[i] > a[i]) ? (currsum + a[i]) : a[i];
        maxsum = (maxsum > currsum) ? maxsum : currsum;     
    }
    cout << maxsum << endl;
    return 0;   
}

分析：时间复杂度为 O（n）。

特别注意：

• 注意解法二与解法三的异同

参考资料：《编程之法》The Art of Programming By July