# 2382. Maximum Segment Sum After Removals      • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public: vector maximumSegmentSum(vector& nums, vector& removeQueries) { const int n = nums.size(); long long maxSum = 0; vector ans(n); // For segment [l, r], record its sum in sum[l] and sum[r] vector sum(n); // For segment [l, r], record its count in count[l] and count[r] vector count(n); for (int i = n - 1; i >= 0; --i) { ans[i] = maxSum; const int j = removeQueries[i]; // Calculate segmentSum const long long leftSum = j > 0 ? sum[j - 1] : 0; const long long rightSum = j + 1 < n ? sum[j + 1] : 0; const long 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 sum and count of 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public long[] maximumSegmentSum(int[] nums, int[] removeQueries) { final int n = nums.length; long maxSum = 0; long[] ans = new long[n]; // For segment [l, r], record its sum in sum[l] and sum[r] long[] sum = new long[n]; // For 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 sum and count of 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution: def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]: n = len(nums) maxSum = 0 ans =  * n # For segment [l, r], record its sum in summ[l] and summ[r] summ =  * n # For segment [l, r], record its count in count[l] and count[r] count =  * 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 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 `