> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1-200/53.-zui-da-zi-xu-he.md).

# 53. 最大子序和

<https://leetcode-cn.com/problems/maximum-subarray/>

## 解法一：暴力

遍历所有长度的连续子段，but超时

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = -sys.maxsize
        for i in range(len(nums)):
            for j in range(i, -1, -1):
                res = max(res, sum(nums[j:i+1]))
        return res
```

## 解法二：dp

![](https://3747312504-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LXItOiQMDgh0S65YZXd%2F-LfAp_veFBwBvew5nXKk%2F-LfApe0S_-OxfKcXdTCo%2F20180614214551620%20\(1\).jpg?alt=media\&token=06991135-e715-411b-914f-5f669eb580d7)

摘自《计算机算法设计与分析》王晓东 第3版

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum = nums[0]  #初始累加和
        b = nums[0]  #dp初始状态，0号
        for i in range(1, len(nums)):  #从1号开始
            if b > 0:
                b += nums[i]
            else:
                b = nums[i]
            sum = max(b, sum)
        return sum
```

2020.3.29

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        res = nums[0]
        if n == 1:
            return res
        dp[0] = nums[0]    #初始
        #用dp[i]记录0~i处最大子序和（包括i）
        for i in range(1, n):
            if dp[i-1] < 0:    #若前面的和小于0，则舍弃
                dp[i] = nums[i]
            else:
                dp[i] = dp[i-1] + nums[i]
            res = max(res, dp[i])     #更新最大和
        return res
```

2021.10.13 nums\[0..i] 中的「最大的子数组和」为 dp\[i]。

### 问题：能用 dp\[i] 推出 dp\[i+1] 吗？（与300. 最长上升子序列的问题类似）

实际上是不行的，因为子数组一定是连续的，按照我们当前 dp 数组定义，并不能保证 nums\[0..i] 中的最大子数组与 nums\[i+1] 是相邻的，也就没办法从 dp\[i] 推导出 dp\[i+1]。

### 改进：以 nums\[i] 为结尾的「最大子数组和」为 dp\[i]。

```python
class Solution:
    def maxSubArray(self, nums) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        dp = [0] * n
        dp[0] = nums[0]  # 初始
        res = dp[0]

        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            res = max(res, dp[i])
        return res
```

改进：状态压缩 由于迭代过程中只用到dp\[i-1]和dp\[i]，用dp\_0和dp\_1代替节省空间

```python
class Solution:
    def maxSubArray(self, nums) -> int:
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        dp = [0] * n
        dp_0 = nums[0]  # 初始
        res = dp_0

        for i in range(1, n):
            dp_1 = max(nums[i], dp_0 + nums[i])
            dp_0 = dp_1
            res = max(res, dp_0)
        return res
```