求最大子数组和的算法

比如对于数组[1,-2,3,5,-1,2] 最大子数组和是sum[3,5,-1,2] = 9, 我们要求函数输出子数组和的最大值,并且返回子数组的左右边界(下面函数的left和right参数).

本文我们规定当数组中所有数都小于0时，返回数组中最大的数（也可以规定返回0，只要让以下代码中maxsum初始化为0即可，此时我们要注意-1 0 0 0 -2这种情形，特别是如果要求输出子数组的起始位置时，如果是面试就要和面试官问清楚）

以下代码我们在PAT 1007. Maximum Subsequence Sum测试通过,测试main函数如下

int main()
{
    int n;
    scanf("%d", &n);
    vector<int>vec(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &vec[i]);
    int left, right;
    int maxsum = maxSum1(vec, left, right);//测试时替换函数名称
    if(maxsum >= 0)
        printf("%d %d %d", maxsum, vec[left], vec[right]);
    else printf("0 %d %d", vec[0], vec[n-1]);
}

参考：编程之美2.14 求数组的子数组之和的最大值

算法1：最简单的就是穷举所有的子数组，然后求和，复杂度是O（n^3）

int maxSum1(vector<int>&vec, int &left, int &right)
{
    int maxsum = INT_MIN, sum = 0;
    for(int i = 0; i < vec.size(); i++)
        for(int k = i; k < vec.size(); k++)
        {
            sum = 0;
            for(int j = i; j <= k; j++)
                sum += vec[j];
            if(sum > maxsum)
            {
                maxsum = sum;
                left = i;
                right = k;
            }
        }
    return maxsum;
}

算法2: 上面代码第三重循环做了很多的重复工作,稍稍改进如下,复杂度为O(n^2)

int maxSum2(vector<int>&vec, int &left, int &right)
{
    int maxsum = INT_MIN, sum = 0;
    for(int i = 0; i < vec.size(); i++)
    {
        sum = 0;
        for(int k = i; k < vec.size(); k++)
        {
            sum += vec[k];
            if(sum > maxsum)
            {
                maxsum = sum;
                left = i;
                right = k;
            }
        }
    }
    return maxsum;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， int
， 函数
， 求代码
， sum
， left
， right
， 数组最大值
， 子数组
求小于n
贪心算法 最大子数组、算法导论 最大子数组、最大完全子图算法、最大公因子算法、最大子序列和联机算法，以便于您获取更多的相关知识。