> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/subarray-sum/maximum_subarray.md).

# 53. Maximum Subarray

https\://leetcode.com/problems/maximum-subarray/description/

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

**Example:**

```
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

**Follow up:**

If you have figured out the O(*n*) solution, try coding another solution using the divide and conquer approach, which is more subtle.

##

问和最大的子数组的和是多少。max + subarray => DP/窗口。 dp\[i]为以i为结尾的最长连续子数组的长度，action为是单独形成一个新subarray还是和前面的拼一起，取决于上一个最优是否为负。

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp, res = 0, float('-inf')
        for _, v in enumerate(nums):
            dp = max(dp, 0) + v
            res = max(dp, res)
        return res
```