2025-07-17:删除所有值为某个元素后的最大子数组和。用go语言,给定一个整数数组 nums,你可以进行以下操作最多一次:
请你计算并返回,在执行上述操作后,所有可能得到的数组中的最大子数组和。
1 <= nums.length <= 100000。
-1000000 <= nums[i] <= 1000000。
输入:nums = [-3,2,-2,-1,3,-2,3]。
输出:7。
解释:
我们执行至多一次操作后可以得到以下数组:
原数组是 nums = [-3, 2, -2, -1, 3, -2, 3] 。最大子数组和为 3 + (-2) + 3 = 4 。
删除所有 X = -3 后得到 nums = [2, -2, -1, 3, -2, 3] 。最大子数组和为 3 + (-2) + 3 = 4 。
删除所有 X = -2 后得到 nums = [-3, 2, -1, 3, 3] 。最大子数组和为 2 + (-1) + 3 + 3 = 7 。
删除所有 X = -1 后得到 nums = [-3, 2, -2, 3, -2, 3] 。最大子数组和为 3 + (-2) + 3 = 4 。
删除所有 X = 3 后得到 nums = [-3, 2, -2, -1, -2] 。最大子数组和为 2 。
输出为 max(4, 4, 7, 4, 2) = 7 。
题目来自力扣3410。
以 nums = [-3, 2, -2, -1, 3, -2, 3]
为例:
3 + (-2) + 3 = 4
。X = -3
:[2, -2, -1, 3, -2, 3]
。3 + (-2) + 3 = 4
。X = -2
:[-3, 2, -1, 3, 3]
。2 + (-1) + 3 + 3 = 7
。X = -1
:[-3, 2, -2, 3, -2, 3]
。3 + (-2) + 3 = 4
。X = 3
:[-3, 2, -2, -1, -2]
。2
。
最终结果为 max(4, 4, 7, 4, 2) = 7
。X
后求最大子数组和,因此需要更高效的方法。X
的影响:X
会移除数组中所有等于 X
的元素。X
后的最大子数组和,并取最大值。X
并重新计算最大子数组和的时间复杂度为 (O(n^2)),对于 (n \leq 10^5) 不可行。X
(即数组中所有不同的元素)。X
,记录其在数组中的位置。originalMax
。X
后的最大子数组和:X
,删除所有 X
后,数组会被分割成若干段。prefixMax
和 suffixMax
数组,分别表示从前往后和从后往前的最大子数组和。X
后,数组被分割为多个不连续的段,最大子数组和可能是:X
是负数)。X
,计算删除 X
后的最大子数组和 currentMax
。max(originalMax, max(currentMax for all X))
。X
:X
。X
后的最大子数组和:prefixMax
和 suffixMax
数组,(O(n)) 时间。X
,计算分割后的最大子数组和:X
的处理时间为 (O(k)),其中 k
是该 X
的出现次数。X
的总处理时间为 (O(n))(因为每个元素最多被处理一次)。X
+ Kadane + 预处理 + 处理所有 X
)。X
的位置:prefixMax
和 suffixMax
数组:.
package main
import (
"fmt"
"math"
)
func maxSubarraySum(nums []int)int64 {
ans := math.MinInt
var s, nonDelMinS, allMin int
delMinS := map[int]int{}
for _, x := range nums {
s += x
ans = max(ans, s-allMin)
if x < 0 {
delMinS[x] = min(delMinS[x], nonDelMinS) + x
allMin = min(allMin, delMinS[x])
nonDelMinS = min(nonDelMinS, s)
}
}
returnint64(ans)
}
func main() {
nums := []int{-3, 2, -2, -1, 3, -2, 3}
result := maxSubarraySum(nums)
fmt.Println(result)
}
# -*-coding:utf-8-*-
import math
def max_subarray_sum(nums):
ans = -math.inf
s = 0
non_del_min_s = 0
all_min = 0
del_min_s = {}
for x in nums:
s += x
ans = max(ans, s - all_min)
if x < 0:
if x not in del_min_s:
del_min_s[x] = non_del_min_s + x
else:
del_min_s[x] = min(del_min_s[x], non_del_min_s) + x
all_min = min(all_min, del_min_s[x])
non_del_min_s = min(non_del_min_s, s)
return ans
if __name__ == "__main__":
nums = [-3, 2, -2, -1, 3, -2, 3]
result = max_subarray_sum(nums)
print(result)
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”,并致力于分享全面的编程知识。在这里,您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。