题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1]的和最大，为 6。
解决方案
对于此题，将采用动态规划进行分析：
对数组的每一个下标所能得到的最大值进行记录；
通过判断上一个下标的最大值是否大于0，大于0则用当前下标所对应的值加上上一个下标。反之，小于则不取上一个下标的最大值(因为若是上一个下标所对应的数组最大值小于0，那么当前下标的数组最大和就等于它本身)。
动态递推公式：dp[i] = max(dp[i-1], 0)+nums[i]
代码示例：
class Solution:def maxSubArray(self, nums: List[int]) -> int:dp = [0 for _ in range(len(nums))]dp[0], max_sums = nums[0], nums[0]for i in range(1, len(nums)):dp[i] = max(dp[i-1], 0)+nums[i]max_sums = max(max_sums, dp[i])return max_sums |
|---|
结语
本题是一道简单的动态规划的题目，更多的是对动态规划的理解与记忆，希望对读者有所帮助。
