连续子数组的最大和

关键词：数组、动态规划

题目描述

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

要求时间复杂度为O(n)。

示例 1：

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解法

解法一：

思路：

• 负数加上任何数都会比数本身小，所以当前的子数组和为负数的时候，就保存负数之前的值并与当前最大值对比，确定新的最大值，子数组和归零。

算法流程：

1. 新建数组res等于原数组；
2. 如果res[i - 1]为正数时，则加到之后的res[i]中；
3. 返回res中的最大值。

代码：

int maxSubArray(vector<int> &nums)
{
    vector<int> res = nums;
    int n = nums.size();
    for (int i = 1; i < n; i++)
        if (res[i - 1] > 0)
            res[i] = nums[i] + res[i - 1];
    return *max_element(res.begin(), res.end());
}

解法二：

思路：

同上。

算法流程：

1. 如果数组元素的个数为0或1时，直接返回对应结果；
2. 初始化最大值与当前子数组和为数组第一个元素；
3. 如果sum<0，则sum归零；
4. 如果sum>max，则更新max；
5. 返回max

代码：

int maxSubArray(vector<int> &nums)
{
    if (nums.size() < 1)
        return 0;
    if (nums.size() == 1)
        return nums[0];
    int max = nums[0];
    int sum = nums[0];
    for (int i = 1; i < nums.size(); i++)
    {
        if (sum < 0)
            sum = 0;
        sum += nums[i];
        if (sum > max)
            max = sum;
    }
    return max;
}

知识点

1. max_element函数的使用
2. 动态规划