设计师网站模版,台州网站制作方案,哈尔滨短视频运营,外网怎么进入参考资料#xff1a; 考点#xff1a;子串 动态规划 [题干] Input: nums [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.1. 心路历程 这道题非常经典#xff0c;蕴含的思想也是精巧无比。 2. 正解 简单来说官… 参考资料 考点子串 动态规划 [题干] Input: nums [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.1. 心路历程 这道题非常经典蕴含的思想也是精巧无比。 2. 正解 简单来说官解就是找到了题目中的无后效性和问题的可分解性(动归) 1)首先分解问题 一个数组中的子串是相当多的穷举显然不是理想的做法那么最大的子串和等于什么答等于以每个数结尾的最大子串的最大值。以数组[-2,1,-3]为例就是以-2为结尾的子串的最大值以1为结尾的子串的最大值和以3为结尾的子串的最大值。这三个最大值中的最大值显然就是原始字符串的最大值。我们可以敏锐的发现以XX为结尾的子串的最大值这一个问题是很容易拆分的。比如以1为结尾的子串的最大值就等于“以-2为结尾的子串的最大值加上1”和“1”之间的大者。显然可以记这个函数“以每个数结尾的最大子串的最大值”为F。 2)确定F的递推公式 还是以数组[-2, 1, -3]为例F[0] -2我们有F[n 1] max(F[n] nums[n1], nums[n1]) 将F[n]都算出来后他们中的最大值显然就是我们想要的结果了。 代码如下 class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: intf nums[0]l len(nums)maxAns nums[0]# f[i] (f[i-1] nums[i], nums[i])for i in range(1, l):f max(f nums[i], nums[i])maxAns max(maxAns, f)return maxAns
