42.连续子数组的最大和

一、 题目

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

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

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

1 <= arr.length <= 10^5

-100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、 解法一：找规律图解

1

如图中，纵坐标表示的是累加和，绿色代表的是我们需要求的最大子数组和。我们发现下面的规律：

• 我们需要找的是整体呈上升趋势的分段

  • 即：区段内的累加和大于0

• 如果区段内的累加和小于0那么当前区段是呈下降趋势的

  • 这段我们可以丢弃，即将累加和重置

• 分析出这样的规律后我们就可以编码了

func maxSubArray(_ nums: [Int]) -> Int {
    var currentSum = nums[0]
    var maxSum = nums[0]
    
    for idx in 1..<nums.count {
        if currentSum < 0 { // 前面的是下降趋势，丢弃之前的
            currentSum = nums[idx]
        }
        else {
            currentSum += nums[idx]
        }
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}

2

三、解法二：动态规划

如果用函数 f(i) 代表第i个数子结尾的子数组最大和，那么有下面的关系：

• i == 0 或者 f(i-1) <= 0

  • f(i) = nums[i]

• else

  • f(i) = f(i-1) + nums[i]

转化成代码：

func maxSubArray(_ nums: [Int]) -> Int {
    var dp: [Int] = Array(repeating: 0, count: nums.count)

    for i in 0..<nums.count {
        if i == 0 || (i > 0 && dp[i-1] <= 0) {
            dp[i] = nums[i]
        }
        else {
            dp[i] = dp[i - 1] + nums[i]
        }
    }

    return dp.max() ?? nums[0]
}

3

四、 总结

• 本题考查对时间复杂度的理解。如果给出 O(n2) O(n3) 的算法，是很难通过面试的。

• 考察队动态规划的理解，如果熟练掌握动态规划算法，那么就可以轻松的找到解题方案。

• 如果没有想到使用动态规划，通过分析计算过程寻找规律同样可以找到解法。