# 53. 最大子序和
## 解法一：暴力
遍历所有长度的连续子段，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
.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
```
---
# 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://cai-sen-se.gitbook.io/leetcode/1-200/53.-zui-da-zi-xu-he.md?ask=
```
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.