# \[53]\[简单]\[动态规划]\[分治] 最大子序和

## 题目描述

[53. 最大子序和](https://leetcode-cn.com/problems/maximum-subarray/) [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)

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

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

## 解题思路

[解题思路: 最大子序和](https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/)

### 动态规划

用$$f(i)$$状态表示以第$$i$$个数结尾的**连续子数组的最大和**, 显然最后的结果就是$$\max{f(i)}$$.

以第$$i$$个数的角度考虑, 如果能与前一位连在一起, 要求前一位$$f(i-1)$$必须不小于0, 否则与前面相加会变小, 肯定不会是连续最大和对应子数组的一部分. 如果第$$i$$个数是后续某个数连续最大和对应的子序列的一部分, 那肯定是不包含$$i$$之前的部分.

因此对应的状态转移方程为:

$$f(i)=\max{f(i-1)+a\_i, a\_i}$$

得到一个时间复杂度为$$O(n)$$, 空间复杂度为$$O(n)$$的算法.

可以使用**滚动数组**思想, 进一步节省空间. 由于每一步只使用上一步的结果, 因此只要保存上一步的$$f$$即可, 空间复杂度压缩为$$O(1)$$.

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        a, total = -1e12, -1e12
        for num in nums:
            a = max(num + a, num)
            total = max(a, total)
        return total
```

### 分治

分治的思路参考[解题思路: 最大子序和](https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/)中的方法二.

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        l, r, m, s = self.sub_array(nums, 0, n - 1)
        return m

    def sub_array(self, array, start, end):
        if start == end:
            t = array[start]
            return t, t, t, t  # left, right, max, sum

        mid = (start + end) // 2
        ll, lr, lm, ls = self.sub_array(array, start, mid)
        rl, rr, rm, rs = self.sub_array(array, mid + 1, end)
        l = max(ll, ls + rl)
        r = max(rr, rs + lr)
        m = max([lm, rm, lr + rl])
        s = ls + rs
        return l, r, m, s
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/fen-zhi/53-zui-da-zi-xu-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.