给你两个下标从 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] 。
class Solution {
public:
vector<long long> maximumSegmentSum(vector<int>& nums, vector<int>& removeQueries) {
int n = nums.size();
vector<long long> ans(n, 0);
vector<long long> s(n + 2, 0);
for(int i = 0; i < n; i ++) s[i + 1] = s[i] + nums[i];
// 对于每个被删除的下标 找到右边第一个被删除的下标 以及找到左边第一个被删除的下标即可
// 那么这段区间被分成两个部分了
// 右边区间的和 : s[r] - s[pos] 左边区间的和 s[pos] - nums[pos] - s[l];
// 分析需要做什么操作?
// 1.删除区间和的操作 2.添加2个新区间和的操作
// 答案? 所有子段和的最大值
// 即平衡树可以做
multiset<long long> S;
S.insert(s[n]);
set<int> id;
id.insert(0), id.insert(n + 1);
for(int i = 0; i < n; i ++){
int idx = removeQueries[i] + 1;
auto it = id.upper_bound(idx);
int R = *it, L = *prev(it, 1);
id.insert(idx);
S.erase(S.find(s[R - 1] - s[L]));
if(idx - L - 1 > 0) S.insert(s[idx - 1] - s[L]);
if(R - idx - 1 > 0) S.insert(s[R - 1] - s[idx]);
if(S.empty()) ans[i] = 0;
else ans[i] = *prev(S.end()); // 不是S.end(), S.end() 是最后一个元素的下一个位置为空
}
return ans;
}
};