LeetCode-53.最大子数组和

发表于 分类于

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例

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

提示

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

题解

动态规划

1
2
3
4
5
6
7
8
9
func maxSubArray(_ nums: [Int]) -> Int {
  var pre = 0
  var maxValue = nums[0]  
  nums.forEach { item in
    pre = max(pre + item, item) // pre: 到达当前位置时，包含当前元素的最大连续子数组和
    maxValue = max(pre, maxValue) // maxValue:最大连续子数组和
  }
  return maxValue
}

如果需要返回这个最大的连续子数组，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxSubArray2(_ nums: [Int]) -> [Int] {
  var pre = 0
  var maxValue = nums[0]
  var start = 0 // 最大连续子数组的起始位置
  var end = 0 // 最大连续子数组的结束位置
  for (idx, val) in nums.enumerated() {
    if pre < 0 {
      pre = val
      if pre > maxValue {
        maxValue = pre
        start = idx
        end = idx
      }
      
    } else {
      pre = pre + val
      if pre > maxValue {
        maxValue = pre
        end = idx
      }
    }
  }
  return Array(nums[start...end])
}