python hot 100——4 动态规划

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]，有两种情况：

1. 接在前面的子数组后面。
2. 不要前面的部分，从当前数字重新开始。

状态转移公式：

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]

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 "最大子数组和是：", answer

4. 🛠 超详细代码逐行讲解

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 基础知识总结

6. 🚨 易错点提醒