53. 最大子数组和
1. 📖 题目要求
给你一个整数数组nums，找出和最大的连续子数组，返回这个子数组的元素和。
例如：
- 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
- 输出：6
- 和最大的连续子数组是： [4,-1,2,1]
- 它的和为：4 + (-1) + 2 + 1 = 6
2. 💡 整体思路
定义数组：f[i]
表示：
必须以
nums[i]结尾的最大子数组和。
对于当前数字nums[i]，有两种情况：
- 接在前面的子数组后面。
- 不要前面的部分，从当前数字重新开始。
状态转移公式：
f[i] = max(f[i - 1], 0) + nums[i]
如果f[i-1]：
- 大于
0：保留前面的子数组。 - 小于
0：前面的部分会拖累结果，直接丢掉。
初始条件：
f[0] = nums[0]最终答案：
max(f)因为最大子数组不一定以最后一个数字结尾。
✏️ 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]i | nums[i] | f[i] |
|---|---|---|
| 0 | -2 | -2 |
| 1 | 1 | 1 |
| 2 | -3 | -2 |
| 3 | 4 | 4 |
| 4 | -1 | 3 |
| 5 | 2 | 5 |
| 6 | 1 | 6 |
| 7 | -5 | 1 |
| 8 | 4 | 5 |
f中的最大值是6。
3. ✅ 可以直接运行的完整程序
class Solution(object): def maxSubArray(self, nums): n=len(nums) f = [0] * n f[0] = nums[0] for i in range(1, n): f[i] = max(f[i - 1], 0) + nums[i] return max(f) text = raw_input("请输入数组：") nums = map(int, text.split()) solution = Solution() answer = solution.maxSubArray(nums) print "最大子数组和是：", answer4. 🛠 超详细代码逐行讲解
class Solution(object): def maxSubArray(self, nums): n=len(nums) f = [0] * n # 创建和nums长度相同的动态规划数组 #初始状态 f[0] = nums[0] # 以第一个数字结尾时，只能选择第一个数字 for i in range(1, n): # 遍历数组下标，从1到最后 #状态转移方程 f[i] = max(f[i - 1], 0) + nums[i] # 如果前面的和大于0，就保留前面的部分 # 如果前面的和小于0，就从当前数字重新开始 return max(f) # 返回f数组中的最大值核心状态转移方程：
f[i] = max(f[i - 1], 0) + nums[i]例如当前数字是4，前面的最大和是-2：
f[i] = max(-2, 0) + 4 = 0 + 4 = 4前面的和是负数，所以从4重新开始。
①为什么不能for i in f:
for i in f:这里的i是f中的元素值，不是下标。
这道题需要通过下标访问：
f[i - 1] # 前一个状态 nums[i] # 当前数字 f[i] # 保存当前状态5. 📚 本题用到的 Python 基础知识总结
| 知识点 | 用法 | 解释 |
|---|---|---|
| 列表 | f = [0] * len(nums) | 创建指定长度的列表 |
| 列表长度 | len(nums) | 获得数组长度 |
for循环 | for i in range(1,n) | 从1到n-1遍历 |
| range | range(a, b)：从a开始，到b-1结束 | 左闭右开 |
6. 🚨 易错点提醒
| 易错点 | 原因 | 正确做法 |
|---|---|---|
f[0]初始化为0 | 子数组不能为空 | f[0] = nums[0] |
| 循环从0开始 | 会访问f[-1] | 从i = 1开始 |
返回f[-1] | 最大子数组不一定以最后一个数字结尾 | 返回max(f) |
| 把子数组当成子序列 | 子数组中的元素必须连续 | 只能与前一个状态拼接 |
| 前面的和为负数还保留 | 负数会拖累当前结果 | 使用max(f[i-1], 0) |
| 答案初始化为0 | 数组可能全部是负数 | 使用f[0] = nums[0] |
