dp连续子数组的最大和求解
2021-04-09 17:26
标签：bar 表示 最大 ret turn sid range 产生 正数 dp连续子数组的最大和求解 标签：bar 表示 最大 ret turn sid range 产生 正数 原文地址：https://www.cnblogs.com/cheslee/p/13374168.htmldp连续子数组的最大问题求解：
思路：
1.dp[i] 表示以第i个元素为末尾元素的子序列最大和
2.只有一个元素时，该元素即最大
3.当dp[i-1]为负数时，对第i个元素产生负影响；为正数时，比较加上第i个元素值是否变大，dp[i] 为nums[i]与dp[i-1]+nums[i]中较大的元素
状态方程：
dp[i] = nums[i] ;dp[i-1]
dp[i] = max(dp[i-1]+nums[i],nums[i]);dp[i-1] > 0
例题：
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0 for i in range(len(nums))]
if len(nums) == 1: # 只有一个元素，选定该元素
return nums[0]
dp[0] = nums[0]
for i in range(1,len(nums)):
if dp[i-1] mmax:
mmax = dp[i]
return mmax
上一篇：python控制流程
下一篇：如何快速掌握一门语言