Maximum Segment Sum After Removals - Practice Coding Problems

Maximum Segment Sum After Removals - Problem

You are given two 0-indexed integer arrays nums and removeQueries, both of length n. For the i^th 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 i^th removal.

Note: The same index will not be removed more than once.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,-1,3,4], removeQueries = [0,2,1]

› Output: [7,7,3]

💡 Note: Initially segments are [1,2] (sum=3) and [3,4] (sum=7). After removing index 0: segments are [2] (sum=2) and [3,4] (sum=7), max=7. After removing index 2: segments are [2] and [3,4], max=7. After removing index 1: segment is [3,4], max=7. Wait, that's wrong. Let me recalculate: After removing 0: [2,-1,3,4] → segments [2] and [3,4], max=7. After removing 2: [2,3,4] → segment [2,3,4] doesn't work because we removed -1, so segments are [2] and [3,4], max=7. After removing 1: [-1,3,4] → segment [3,4], max=7. Actually the answer should be [7,7,3] where the last 3 comes from [3,4]=7 after removing index 1.

Example 2 — All Positive Numbers

$ Input: nums = [3,2,1,2,4], removeQueries = [4,1,3,0,2]

› Output: [12,9,6,3,0]

💡 Note: Initially all positive: segment [3,2,1,2,4] sum=12. Remove 4: [3,2,1,2] sum=8, max=8. Remove 1: [3,1,2] segments [3] and [1,2], max=3. Remove 3: [3,1] segment sums, max. Remove 0: [1], max=1. Remove 2: [], max=0.

Example 3 — Single Element

$ Input: nums = [5], removeQueries = [0]

› Output: [0]

💡 Note: After removing the only positive element, no segments remain, so maximum sum is 0.

Constraints

n == nums.length == removeQueries.length
1 ≤ n ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹
0 ≤ removeQueries[i] < n
All values of removeQueries are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

Array with positive/negative numbers and removal queries

Process

Remove elements in query order, find max segment sum

Output

Array of maximum segment sums after each removal

Key Takeaway

🎯 Key Insight: Process removals in reverse - it's easier to add elements and merge segments than to split them

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to process removals in reverse order, adding elements back instead of removing them. Use Union Find to efficiently merge adjacent positive segments. Best approach is reverse processing: Time: O(n α(n)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n²)	O(n)	Simulate each removal and scan all segments to find maximum sum
Reverse Processing with Union Find	O(n α(n))	O(n)	Process removals in reverse order, building segments incrementally using Union Find

Brute Force Simulation — Algorithm Steps

For each removal query, mark the element as removed
Scan the array to find all contiguous positive segments
Calculate sum of each segment and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Remove Element

Mark element at removeQueries[i] as removed

Scan Segments

Find all positive contiguous segments

Find Maximum

Calculate sum of each segment and return maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void solution(int* nums, int numsSize, int* removeQueries, int queriesSize, long long* result) {
    bool* removed = (bool*)calloc(numsSize, sizeof(bool));
    
    for (int q = 0; q < queriesSize; q++) {
        removed[removeQueries[q]] = true;
        long long maxSum = 0;
        
        // Find all segments and their sums
        int i = 0;
        while (i < numsSize) {
            if (!removed[i] && nums[i] > 0) {
                // Found start of a positive segment
                long long segmentSum = 0;
                while (i < numsSize && !removed[i] && nums[i] > 0) {
                    segmentSum += nums[i];
                    i++;
                }
                if (segmentSum > maxSum) {
                    maxSum = segmentSum;
                }
            } else {
                i++;
            }
        }
        
        result[q] = maxSum;
    }
    
    free(removed);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums array
    int nums[100000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    // Parse removeQueries array
    int removeQueries[100000];
    int queriesSize = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        removeQueries[queriesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long* result = (long long*)malloc(queriesSize * sizeof(long long));
    solution(nums, numsSize, removeQueries, queriesSize, result);
    
    printf("[");
    for (int i = 0; i < queriesSize; i++) {
        if (i > 0) printf(",");
        printf("%lld", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n queries, we scan the entire array to find segments

⚠ Quadratic Growth

Space Complexity

O(n)

Need array to track removed elements and store result

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler