Maximize Subarray Sum After Removing All Occurrences of One Element

Maximize Subarray Sum After Removing All Occurrences of One Element - Problem

You are given an integer array nums. You can do the following operation on the array at most once:

Choose any integer x such that nums remains non-empty on removing all occurrences of x.
Remove all occurrences of x from the array.

Return the maximum subarray sum across all possible resulting arrays.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Remove Negative Elements

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

› Output: 4

💡 Note: Remove all occurrences of -3 to get [1, 2, 1]. The maximum subarray sum is 1 + 2 + 1 = 4.

Example 2 — Remove Positive Elements

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

› Output: 2

💡 Note: We can remove -3 to get [1, -4, 2] (max sum = 2), or remove -4 to get [1, -3, 2] (max sum = 2), or remove 1 to get [-3, -4, 2] (max sum = 2). Best result is 2.

Example 3 — All Elements Same

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

› Output: 15

💡 Note: Cannot remove all 5s (array must remain non-empty). Original array has max subarray sum of 5+5+5+5 = 20. But we must remove at least one occurrence. Actually, we don't have to remove any element, so answer is 20. Wait - re-reading: we can do the operation "at most once", meaning 0 or 1 times. So answer is 20.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
The resulting array must be non-empty

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with positive and negative elements

Try Removals

Test removing each unique element

Best Result

Find the removal that gives maximum subarray sum

Key Takeaway

🎯 Key Insight: Remove elements that break up positive sequences or contribute large negative values to maximize the resulting subarray sum

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is that we want to remove elements that either break up positive sequences or contribute large negative values. The optimal approach tries removing each unique element and finds the maximum subarray sum using Kadane's algorithm. Time: O(n³) brute force, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Prefix/Suffix Sums	O(n²)	O(n)	Use prefix and suffix maximum subarray sums to avoid recomputation
Brute Force - Try All Removals	O(n³)	O(n)	For each unique value, remove it and find maximum subarray sum

Optimized with Prefix/Suffix Sums — Algorithm Steps

Compute prefix max subarray sums from left
Compute suffix max subarray sums from right
For each unique element, find max sum by combining prefix/suffix
Handle edge cases where element appears at boundaries

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Segments

Split array into segments separated by target value

Concatenate

Join all segments into one array

Apply Kadane

Find maximum subarray sum in concatenated result

Code -

solution.c — C

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

int kadane(int* arr, int n) {
    if (n == 0) return INT_MIN;
    int maxSum = arr[0];
    int currSum = arr[0];
    for (int i = 1; i < n; i++) {
        currSum = (currSum + arr[i] > arr[i]) ? currSum + arr[i] : arr[i];
        maxSum = (currSum > maxSum) ? currSum : maxSum;
    }
    return maxSum;
}

int solution(int* nums, int n) {
    if (n == 0) return 0;
    if (n == 1) return 0; // Must remove the only element
    
    int maxResult = kadane(nums, n); // Original array max subarray
    
    // Try removing each unique value
    for (int i = 0; i < n; i++) {
        int val = nums[i];
        
        // Check if we already processed this value
        int alreadyProcessed = 0;
        for (int j = 0; j < i; j++) {
            if (nums[j] == val) {
                alreadyProcessed = 1;
                break;
            }
        }
        if (alreadyProcessed) continue;
        
        // Create array without val
        int* filtered = malloc(n * sizeof(int));
        int filteredSize = 0;
        
        for (int j = 0; j < n; j++) {
            if (nums[j] != val) {
                filtered[filteredSize++] = nums[j];
            }
        }
        
        if (filteredSize > 0) {
            int result = kadane(filtered, filteredSize);
            if (result > maxResult) {
                maxResult = result;
            }
        }
        
        free(filtered);
    }
    
    return maxResult;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int nums[1000];
    int n = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            nums[n++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) for preprocessing + O(n) unique elements × O(n) to process each removal

⚠ Quadratic Growth

Space Complexity

O(n)

Arrays for prefix/suffix sums and unique values set

⚡ Linearithmic Space

23.8K Views

Medium Frequency

~25 min Avg. Time

850 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

Optimized with Prefix/Suffix Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler