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 62. 整体思路定义数组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]inums[i]f[i]0-2-21112-3-23444-135256167-51845f中的最大值是6。3. ✅ 可以直接运行的完整程序class Solution(object): def maxSubArray(self, nums): nlen(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): nlen(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前面的最大和是-2f[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遍历rangerange(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]