Leetcode题53、最大子序和（Python题解）字节跳动面试题

问题：

题目来源：力扣（LeetCode）

leetcode53.最大子序和

难度：简单

分析： 可以用DP和分治做。 在本题中分治的做法更复杂、时间更长，但在某些背景下却被认为是更优的做法。这是为什么呢？ 因为分治法不仅可以解决区间[0, n - 1]的问题，还可以解决任意区间 [l, r]的问题。如果在计算过程中将结果用堆都存储下来。那么就可在O（logn)的时间内求取任意时间的答案。

解决方法： 1：常规思路 用两个值记录遍历过程中的结果，不断求取最大值。 无论是常规思路还是DP，遵循的一个原则是：当某元素之前的子序和小于等于0的时候，那么前面的子序和对子序和的增加没有贡献，前述子序结束，当前子序重新开始。

#DP，常规思路 class Solution: def maxSubArray(self, nums: List[int]) -> int: sum_temp = 0 sum_max = nums[0] for i in range(len(nums)): if sum_temp >= 0: sum_temp += nums[i] else: sum_temp = nums[i] sum_max = max(sum_max, sum_temp) return sum_max

2：DP DP的状态空间设定为： dp[i]是数组中每个位置存的是以当前值为结尾的最大子序列和，因此最后求max就得到整个数组中的最大子序列和。 这个状态空间的理解特别重要！寻找最大子序和的过程并不是一个连续的过程，只局部子序连续，在不同子序间需要丢掉前一个子序和，计算后一个子序和。 当然我们也可以在求的过程中再加一个变量来记录最大子序和，不过最后直接取max更快更直接。 递推公式为 if dp[i - 1] <= 0：dp[i] = nums[i]， if dp[i - 1] > 0: dp[i] = dp[i - 1] + nums[i]，

class Solution: def maxSubArray(self, nums: List[int]) -> int: dp=[0]*(len(nums)) dp[0]=nums[0] for i in range(1,len(nums)): if dp[i-1]<=0: dp[i]=nums[i] else: dp[i]=dp[i-1]+nums[i] return max(dp)

3：DP原地操作 直接在原数组上操作。 递推公式为 dp[i] = max(dp[i - 1] + nums[i]，nums[i]) max操作直接隐含了当dp[i - 1] <= 0时，nums[i]; 当dp[i - 1] > 0时，取dp[i - 1] + nums[i]。

class Solution: def maxSubArray(self, nums: List[int]) -> int: for i in range(1, len(nums)): nums[i] = max(nums[i - 1] + nums[i], nums[i]) return max(nums)

4：分治 分治是求左半边最大子序和、右半边最大子序和、以及穿越中点的最大子序和。

class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) # 递归终止条件 if n == 1: return nums[0] else: # 递归计算左半边最大子序和 max_left = self.maxSubArray(nums[0:len(nums) // 2]) # 递归计算右半边最大子序和 max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)]) # 计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加 max_l = nums[len(nums) // 2 - 1] tmp = 0 for i in range(len(nums) // 2 - 1, -1, -1): tmp += nums[i] max_l = max(tmp, max_l) max_r = nums[len(nums) // 2] tmp = 0 for i in range(len(nums) // 2, len(nums)): tmp += nums[i] max_r = max(tmp, max_r) # 返回三个中的最大值 return max(max_right, max_left, max_l + max_r)