You are given two 0-indexed integer arrays nums and removeQueries, both of length n. For the ith query, the element in nums at the index removeQueries[i] is removed, splitting nums into different segments.
A segment is a contiguous sequence of positive integers in nums. A segment sum is the sum of every element in a segment.
Return an integer array answer, of length n, where answer[i] is the maximum segment sum after applying the ith removal.
Note: The same index will not be removed more than once.
Example 1:
Input: nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
Output: [14,7,2,2,0]
Explanation: Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1].
Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5].
Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2].
Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2].
Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [14,7,2,2,0].
Example 2:
Input: nums = [3,2,11,1], removeQueries = [3,2,1,0]
Output: [16,5,3,0]
Explanation: Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11].
Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2].
Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3].
Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [16,5,3,0].
Constraints:
n == nums.length == removeQueries.length1 <= n <= 1051 <= nums[i] <= 1090 <= removeQueries[i] < n- All the values of
removeQueries are unique.
Java Code :
class Solution {
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
int n = nums.length;
long[] result = new long[n]; // array to store answer
long[] prefixSum = new long[n+1]; // array to store prefixSum of nums
// calculating prefixSum
for(int i = 0; i < n; i++){
prefixSum[i+1] = prefixSum[i] + nums[i];
}
// TreeMap to store ranges to its sum mapping
TreeMap<int[], Long> ranges = new TreeMap<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
// initially it will have whole array range
ranges.put(new int[]{0, n - 1}, prefixSum[n]);
// TreeMap to store all the possible sums of range we encounter while solving queries, we are storing frequencies because
// multiple range can have same sum.
TreeMap<Long, Integer> sums = new TreeMap<>();
// initialise it with sum of all array.
sums.put(prefixSum[n], 1);
// Iterating on queries
for(int i = 0; i < n; i++){
int node = removeQueries[i]; // index to be removed or set to zero.
// finding range which will split when node index is removed or set 0.
int[] rangeToBeRemoved = ranges.floorKey(new int[]{node});
Long sum = ranges.get(rangeToBeRemoved); // finding its sum
// removing/ reducing sum from sums Map because we are splitting that range, so it is no more valid
int f = sums.get(sum);
if(f == 1) sums.remove(sum);
else sums.put(sum, f - 1);
// removing that range
ranges.remove(rangeToBeRemoved);
int l = rangeToBeRemoved[0];
int r = rangeToBeRemoved[1];
long newSum = 0;
// Splitting range and store back new ranges form along with its sum.
if (l == node && r != node) {
newSum = prefixSum[r + 1] - prefixSum[l + 1];
ranges.put(new int[]{l+1, r}, newSum);
sums.put(newSum, sums.getOrDefault(newSum, 0) + 1);
} else if (r == node && l != node) {
newSum = prefixSum[r] - prefixSum[l];
ranges.put(new int[]{l, r - 1}, newSum);
sums.put(newSum, sums.getOrDefault(newSum, 0) + 1);
} else if(node > l && node < r){
newSum = prefixSum[node] - prefixSum[l];
ranges.put(new int[]{l, node - 1}, newSum);
sums.put(newSum, sums.getOrDefault(newSum, 0) + 1);
newSum = prefixSum[r+1] - prefixSum[node + 1];
ranges.put(new int[]{node + 1, r}, newSum);
sums.put(newSum, sums.getOrDefault(newSum, 0) + 1);
}
if(sums.size() != 0)
result[i] = sums.lastKey();
else
result[i] = 0;
}
return result;
}
}
