LeetCode 最大区间和题解

LeetCode 最大区间和题解题目描述给定一个数组找到任意连续子数组的最大和。示例输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解题思路方法线段树思路使用线段树维护区间的最大前缀和、最大后缀和、最大区间和。合并时计算新的三个值。复杂度分析时间复杂度O(n)。空间复杂度O(n)。代码实现class SegmentTree: def __init__(self, nums): self.n len(nums) self.tree [None] * (4 * self.n) self.build(1, 0, self.n - 1, nums) def build(self, node, l, r, nums): if l r: val nums[l] self.tree[node] (val, val, val, val) else: mid (l r) // 2 self.build(node * 2, l, mid, nums) self.build(node * 2 1, mid 1, r, nums) left self.tree[node * 2] right self.tree[node * 2 1] total left[0] right[0] prefix max(left[1], left[0] right[1]) suffix max(right[2], right[0] left[2]) segment max(left[3], right[3], left[2] right[1]) self.tree[node] (total, prefix, suffix, segment) def query(self): return self.tree[1][3] # 测试 def test_max_subarray(): nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] st SegmentTree(nums) print(st.query()) # 输出6 if __name__ __main__: test_max_subarray()总结线段树可以用于解决最大区间和问题通过维护区间的最大前缀和、最大后缀和、最大区间和来合并结果。