题目
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
我的代码（Python）
version 1
class Solution:
class SubResult:
def __init__(self, front_sub: int, end_sub: int, curr_sub: int, full_sub: int):
self.front_sub = front_sub
self.end_sub = end_sub
self.curr_sub = curr_sub
self.full_sub = full_sub
def calList(self, nums: List[int], startIdx: int, endIdx: int):
if startIdx == endIdx:
return self.SubResult(nums[startIdx], nums[startIdx], nums[startIdx], nums[startIdx])
frontResult = self.calList(nums, startIdx, startIdx + (endIdx - startIdx) // 2)
endResult = self.calList(nums, startIdx + (endIdx - startIdx) // 2 + 1, endIdx)
full_sub = frontResult.full_sub + endResult.full_sub
front_sub = max(frontResult.front_sub, frontResult.full_sub + endResult.front_sub)
end_sub = max(frontResult.end_sub + endResult.full_sub, endResult.end_sub)
curr_sub = max(frontResult.curr_sub, endResult.curr_sub, frontResult.end_sub + endResult.front_sub)
return self.SubResult(front_sub, end_sub, curr_sub, full_sub)
def maxSubArray(self, nums: List[int]) -> int:
result = self.calList(nums, 0, len(nums) - 1)
return max(result.front_sub, result.end_sub, result.curr_sub, result.full_sub)考虑到了分治的算法，结果虽然是通过了，但是时间效率不高，只击败了5%。空间击败了79%，还可以。这种分治算法感觉并不算太好。
version 2
def maxSubArray(self, nums: List[int]) -> int:
currResult = nums[0]
currMaxSum = 0
for i in nums:
currMaxSum = max(currMaxSum + i, i)
currResult = max(currMaxSum, currResult)
return currResult直接计算，这种方案反而更快一些，时间击败58%，空间击败85%。
所以前面的分治算法有问题？
点评
参考官方算法之后，发现我的想法其实是正确的。只不过分治算法的优势不体现在这里，而是体现在可以缓存这些中间结果以备以后计算任意区间的最大和子项。这就是线段树的结构。
baddif@gmail.com
AI简历优化站
求职记录管理系统（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog