出处：https://www.cnblogs.com/waytofall/archive/2012/04/10/2439820.html

问题：

数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值及该数组左右边界。

思路：

设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i] = max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。 C++代码：

//定义结构体使函数返回多值
struct result
{
    int sum;
    int begin;
    int end;
};

result findMax(int a[], int size)
{
    struct result res = {a[0], 0, 0};
    int sum = a[0], i;
    for (i = 1; i < size; i++)
    {
        if (sum > 0)
        {
            sum += a[i];
        }
        else
        {
            sum = a[i];
            res.begin = i;
        }
        if (sum > res.sum)
            res.sum = sum;
        res.end = i;   
    }
    return res;
}

本博客文章仅供博主学习交流，博主才疏学浅，语言表达能力有限，对知识的理解、编写代码能力都有很多不足，希望各路大神多多包涵，多加指教。