| 题目链接 | 53. 最大子数组和 |
|---|---|
| 思路 | 1. 前缀和 2. 动态规划 |
| 题解链接 | 两种方法：前缀和/动态规划（Python/Java/C++/C/Go/JS/Rust） |
| 关键点 | 无 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现（前缀和）：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
answer = -inf
min_presum = 0
presum = 0
for num in nums:
presum += num
answer = max(answer, presum - min_presum)
min_presum = min(min_presum, presum)
return answer
代码实现（动态规划）：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
answer = -inf
dp = 0
for x in nums:
dp = max(dp, 0) + x
answer = max(answer, dp)
return answer