做网站什么字体营销网站建设软件下载
- 题目描述：给你一个整数数组 array:
nums，请你找出一个具有最大和的连续子数组 sub-array，返回其最大和- 子数组（最少包含一个元素）: 是数组中的一个连续部分
-
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6 -
示例 2:
输入：nums = [1]
输出：1 -
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
- 题解：采用动态规划进行求解，以下为动态规划详细步骤分析
- 确定 dp 数组含义：
dp[i]表示包括下标 i（以nums[i]为结尾）的最⼤连续⼦序列和- 注意❌不能表示
nums[: i+1]的最⼤连续⼦序列和 (不一定包括下标i) ！ 否则无法递推！
- 注意❌不能表示
- 确定递推公式：取 断/不断 的最大值
max(nums[i], dp[i-1] + nums[i])- 如果从
nums[i]前断开：则包括下标 i 的最⼤连续⼦序列和为nums[i] - 如果不从
nums[i]断开：则包括下标 i 的最⼤连续⼦序列和为dp[i-1] + nums[i]
- 如果从
- 确定遍历顺序和初始化：从前向后，初始化
dp[0] = nums[0]- 从递推公式可以看出
dp[i]由前序元素dp[i-1]推出，根本是dp[0] - 根据
dp 数组含义,dp[0]表示包括下标 0 的最⼤连续⼦序列和，即只包含nums[0]，所以dp[0] = nums[0]
- 从递推公式可以看出
- 确定 dp 数组含义：
- 完整对应代码：
class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0 for _ in range(len(nums))] ## dp[i] 表示包括下标 i 的最⼤连续⼦序列和dp[0] = nums[0] ## 初始化：dp[0] = nums[0]for i in range(1, len(nums)):dp[i] = max(nums[i], dp[i-1]+nums[i]) ## 递推公式return max(dp)