# 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](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-539aab609f40ff1a830294ee77aec5264e199bc9%2F42-01.png?alt=media)

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

* 我们需要找的是整体呈上升趋势的分段
  * 即：区段内的累加和**大于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](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-d57f4cc6e99b25f4628f5d903cd2a2326d916d68%2F42-02.png?alt=media)

### 三、解法二：动态规划

如果用函数 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](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MI8JgbGh3U6X_oedqkm%2Fuploads%2Fgit-blob-b11bd6bedd0f1e72feef53c0c4cb88d5e5fb09d5%2F42-03.png?alt=media)

### 四、 总结

* 本题考查对时间复杂度的理解。如果给出 O(n2) O(n3) 的算法，是很难通过面试的。
* 考察队动态规划的理解，如果熟练掌握动态规划算法，那么就可以轻松的找到解题方案。
* 如果没有想到使用动态规划，通过分析计算过程寻找规律同样可以找到解法。