2382. Maximum Segment Sum After Removals LeetCode Solution
In this guide, you will get 2382. Maximum Segment Sum After Removals LeetCode Solution with the best time and space complexity. The solution to Maximum Segment Sum After Removals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Segment Sum After Removals
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.length
1 <= n <= 105
1 <= nums[i] <= 109
0 <= removeQueries[i] < n
All the values of removeQueries are unique.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2382. Maximum Segment Sum After Removals LeetCode Solution in C++
class Solution {
public:
vector<long long> maximumSegmentSum(vector<int>& nums,
vector<int>& removeQueries) {
const int n = nums.size();
long maxSum = 0;
vector<long long> ans(n);
// For the segment [l, r], record its sum in sum[l] and sum[r]
vector<long long> sum(n);
// For the segment [l, r], record its count in count[l] and count[r]
vector<int> count(n);
for (int i = n - 1; i >= 0; --i) {
ans[i] = maxSum;
const int j = removeQueries[i];
// Calculate `segmentSum`.
const long leftSum = j > 0 ? sum[j - 1] : 0;
const long rightSum = j + 1 < n ? sum[j + 1] : 0;
const long segmentSum = nums[j] + leftSum + rightSum;
// Calculate `segmentCount`.
const int leftCount = j > 0 ? count[j - 1] : 0;
const int rightCount = j + 1 < n ? count[j + 1] : 0;
const int segmentCount = 1 + leftCount + rightCount;
// Update the sum and count of the segment [l, r].
const int l = j - leftCount;
const int r = j + rightCount;
sum[l] = segmentSum;
sum[r] = segmentSum;
count[l] = segmentCount;
count[r] = segmentCount;
maxSum = max(maxSum, segmentSum);
}
return ans;
}
}; /* code provided by PROGIEZ */
2382. Maximum Segment Sum After Removals LeetCode Solution in Java
class Solution {
public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
final int n = nums.length;
long maxSum = 0;
long[] ans = new long[n];
// For the segment [l, r], record its sum in sum[l] and sum[r]
long[] sum = new long[n];
// For the segment [l, r], record its count in count[l] and count[r]
int[] count = new int[n];
for (int i = n - 1; i >= 0; --i) {
ans[i] = maxSum;
final int j = removeQueries[i];
// Calculate `segmentSum`.
final long leftSum = j > 0 ? sum[j - 1] : 0;
final long rightSum = j + 1 < n ? sum[j + 1] : 0;
final long segmentSum = nums[j] + leftSum + rightSum;
// Calculate `segmentCount`.
final int leftCount = j > 0 ? count[j - 1] : 0;
final int rightCount = j + 1 < n ? count[j + 1] : 0;
final int segmentCount = 1 + leftCount + rightCount;
// Update the sum and count of the segment [l, r].
final int l = j - leftCount;
final int r = j + rightCount;
sum[l] = segmentSum;
sum[r] = segmentSum;
count[l] = segmentCount;
count[r] = segmentCount;
maxSum = Math.max(maxSum, segmentSum);
}
return ans;
}
} // code provided by PROGIEZ
2382. Maximum Segment Sum After Removals LeetCode Solution in Python
class Solution:
def maximumSegmentSum(
self,
nums: list[int],
removeQueries: list[int],
) -> list[int]:
n = len(nums)
maxSum = 0
ans = [0] * n
# For the segment [l, r], record its sum in summ[l] and summ[r]
summ = [0] * n
# For the segment [l, r], record its count in count[l] and count[r]
count = [0] * n
for i in reversed(range(n)):
ans[i] = maxSum
j = removeQueries[i]
# Calculate `segmentSum`.
leftSum = summ[j - 1] if j > 0 else 0
rightSum = summ[j + 1] if j + 1 < n else 0
segmentSum = nums[j] + leftSum + rightSum
# Calculate `segmentCount`.
leftCount = count[j - 1] if j > 0 else 0
rightCount = count[j + 1] if j + 1 < n else 0
segmentCount = 1 + leftCount + rightCount
# Update `summ` and `count` of the segment [l, r].
l = j - leftCount
r = j + rightCount
summ[l] = segmentSum
summ[r] = segmentSum
count[l] = segmentCount
count[r] = segmentCount
maxSum = max(maxSum, segmentSum)
return ans # code by PROGIEZ
