以下是 LeetCode 3410. 删除所有值为某个元素后的最大子数组和 的 Python3 实现。题目理解给定整数数组 nums可以至多一次选择某个值 X删除数组中所有值为 X 的元素删除后数组必须非空求能得到数组的最大子数组和。- 示例1nums [-3,2,-2,-1,3,-2,3]删除所有 -2 后得到 [-3,2,-1,3,3]最大子数组和为 2(-1)33 7。- 示例2nums [1,2,3,4]不删除任何元素最大子数组和为 10。解题思路这道题的核心是线段树维护最大子段和 1. 不删除时就是经典的「最大子数组和」LeetCode 53可用动态规划或线段树解决。2. 删除某个值 X 时等价于将数组中所有值为 X 的位置设为 0然后求最大子数组和。3. 枚举所有可能的 X用哈希表按值分组记录下标对每个不同的值将其所有出现位置在线段树中更新为 0查询全局最大子段和然后恢复。线段树每个节点需要维护 4 个信息- sm区间总和- lv从区间左边界开始的最大子段和- rv以区间右边界结束的最大子段和- ans区间内的最大子段和合并两个区间时最大子段和有三种来源完全在左区间、完全在右区间、横跨两个区间。注意Python 中这道题卡常需要手写 max 函数用 lambda 或普通函数否则用内置 max 会超时 。Python3 代码pythonclass Node:def __init__(self, sm, lv, rv, ans):self.sm sm # 区间和self.lv lv # 从左边界开始的最大子段和self.rv rv # 以右边界结束的最大子段和self.ans ans # 区间内的最大子段和class Solution:def maxSubarraySum(self, nums):n len(nums)# 特殊情况全是负数时子段必须非空只能选最大的负数mx -10**9for x in nums:mx mx if mx x else xif mx 0:return mx# 手动比大小效率更高不这么写 Python 会超时def mymax(a, b):return b if b a else a# 线段树维护最大子段和tree [Node(0, 0, 0, 0) for _ in range(2 n.bit_length())]def merge(nl, nr):合并两个区间return Node(nl.sm nr.sm,mymax(nl.lv, nl.sm nr.lv), # 左区间左半部分或左边全选右边左部分mymax(nl.rv nr.sm, nr.rv), # 右区间右半部分或左边右部分右边全选mymax(mymax(nl.ans, nr.ans), nl.rv nr.lv) # 左区间、右区间、或横跨)def initNode(val):return Node(val, val, val, val)def build(id, l, r):if l r:tree[id] initNode(nums[l])else:nxt id 1mid (l r) 1build(nxt, l, mid)build(nxt 1, mid 1, r)tree[id] merge(tree[nxt], tree[nxt 1])def modify(id, l, r, pos, val):单点更新将位置 pos 的值改为 valif l r:tree[id] initNode(val)else:nxt id 1mid (l r) 1if pos mid:modify(nxt, l, mid, pos, val)else:modify(nxt 1, mid 1, r, pos, val)tree[id] merge(tree[nxt], tree[nxt 1])# 构建线段树build(1, 0, n - 1)# 不删除任何元素的答案ans tree[1].ans# 按值分组记录每个值出现的所有下标from collections import defaultdictmp defaultdict(list)for i in range(n):mp[nums[i]].append(i)# 枚举删除哪种数for val, indices in mp.items():if len(indices) ! n: # 删除后需要保证数组不为空# 把这种数都改成 0模拟删除for x in indices:modify(1, 0, n - 1, x, 0)# 更新答案ans mymax(ans, tree[1].ans)# 恢复for x in indices:modify(1, 0, n - 1, x, val)return ans复杂度分析- 时间复杂度O(n \log n)构建线段树 O(n \log n)枚举每个不同值并更新 O(k \cdot m \cdot \log n)其中 k 是不同值的个数m 是该值出现次数总和为 O(n \log n)。- 空间复杂度O(n)线段树需要约 4n 个节点。