Links

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) 的算法,是很难通过面试的。
  • 考察队动态规划的理解,如果熟练掌握动态规划算法,那么就可以轻松的找到解题方案。
  • 如果没有想到使用动态规划,通过分析计算过程寻找规律同样可以找到解法。