class Solution {
public:
vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
}
};
2382. 删除操作后的最大子段和
给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。
一个 子段 是 nums 中连续 正 整数形成的序列。子段和 是子段中所有元素的和。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]是第 i 次删除操作以后的 最大 子段和。
注意：一个下标至多只会被删除一次。
示例 1：
输入：nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1] 输出：[14,7,2,2,0] 解释：用 0 表示被删除的元素，答案如下所示： 查询 1 ：删除第 0 个元素，nums 变成 [0,2,5,6,1] ，最大子段和为子段 [2,5,6,1] 的和 14 。 查询 2 ：删除第 3 个元素，nums 变成 [0,2,5,0,1] ，最大子段和为子段 [2,5] 的和 7 。 查询 3 ：删除第 2 个元素，nums 变成 [0,2,0,0,1] ，最大子段和为子段 [2] 的和 2 。 查询 4 ：删除第 4 个元素，nums 变成 [0,2,0,0,0] ，最大子段和为子段 [2] 的和 2 。 查询 5 ：删除第 1 个元素，nums 变成 [0,0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。 所以，我们返回 [14,7,2,2,0] 。
示例 2：
输入：nums = [3,2,11,1], removeQueries = [3,2,1,0] 输出：[16,5,3,0] 解释：用 0 表示被删除的元素，答案如下所示： 查询 1 ：删除第 3 个元素，nums 变成 [3,2,11,0] ，最大子段和为子段 [3,2,11] 的和 16 。 查询 2 ：删除第 2 个元素，nums 变成 [3,2,0,0] ，最大子段和为子段 [3,2] 的和 5 。 查询 3 ：删除第 1 个元素，nums 变成 [3,0,0,0] ，最大子段和为子段 [3] 的和 3 。 查询 5 ：删除第 0 个元素，nums 变成 [0,0,0,0] ，最大子段和为 0 ，因为没有任何子段存在。 所以，我们返回 [16,5,3,0] 。
提示：
n == nums.length == removeQueries.length1 <= n <= 1051 <= nums[i] <= 1090 <= removeQueries[i] < nremoveQueries 中所有数字 互不相同 。原站题解
java 解法, 执行用时: 6 ms, 内存消耗: 67.3 MB, 提交时间: 2023-08-16 17:37:53
class Solution {
int[] fa;
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
var n = nums.length;
fa = new int[n + 1];
for (var i = 0; i <= n; i++) fa[i] = i;
var sum = new long[n + 1];
var ans = new long[n];
for (var i = n - 1; i > 0; --i) {
var x = removeQueries[i];
var to = find(x + 1);
fa[x] = to; // 合并 x 和 x+1
sum[to] += sum[x] + nums[x];
ans[i - 1] = Math.max(ans[i], sum[to]);
}
return ans;
}
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
}
golang 解法, 执行用时: 172 ms, 内存消耗: 12.2 MB, 提交时间: 2023-08-16 17:36:53
func maximumSegmentSum(nums []int, removeQueries []int) (ans []int64) {
n := len(nums)
fa := make([]int, n+1)
for i := range fa {
fa[i] = i
}
sum := make([]int64, n+1)
var find func(int) int
find = func(x int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
ans = make([]int64, n)
for i := n - 1; i > 0; i-- {
x := removeQueries[i]
to := find(x + 1)
fa[x] = to // 合并 x 和 x+1
sum[to] += sum[x] + int64(nums[x])
ans[i-1] = max(ans[i], sum[to])
}
return
}
func max(a, b int64) int64 { if b > a { return b }; return a }
python3 解法, 执行用时: 512 ms, 内存消耗: 43.3 MB, 提交时间: 2023-08-16 17:36:22
'''
删除改为增加，动态维护每个子段的元素和，高效地合并两个子段。
'''
class Solution:
def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
n = len(nums)
fa = [i for i in range(n+1)]
sum = [0] * (n + 1)
def find(x: int) -> int:
if fa[x] != x:
fa[x] = find(fa[x])
return fa[x]
ans = [0] * n
for i in range(n - 1, 0, -1):
x = removeQueries[i]
to = find(x + 1)
fa[x] = to # 合并 x 和 x+1
sum[to] += sum[x] + nums[x]
ans[i - 1] = max(ans[i], sum[to])
return ans