Maximum Subarray Sum with One Deletion - Practice Coding Problems

Maximum Subarray Sum with One Deletion - Problem

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion.

In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: We can choose subarray [2,1,-1] and delete -1 to get [2,1] with sum = 3. Or choose [1,-3,2,1] and delete -3 to get [1,2,1] with sum = 4.

Example 2 — No Deletion Needed

$ Input: arr = [1,-2,0,3]

› Output: 4

💡 Note: We can choose subarray [1,-2,0,3] and delete -2 to get [1,0,3] with sum = 4. Or just take [3] without deletion.

Example 3 — Single Element

$ Input: arr = [-1]

› Output: -1

💡 Note: We must return at least one element. Since we only have [-1], we cannot delete it, so return -1.

Constraints

1 ≤ arr.length ≤ 10⁵
-10⁴ ≤ arr[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,-3,2,1,-1] with negative elements

Find Best Subarray

Consider subarrays with 0 or 1 deletion

Output Maximum

Return 4 by deleting -3 from [1,-3,2,1]

Key Takeaway

🎯 Key Insight: Track two DP states simultaneously - maximum sum with 0 deletions and 1 deletion

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is to use dynamic programming to track two states: maximum subarray sum ending at each position with 0 deletions and with 1 deletion. At each element, we can either extend previous subarrays or start new ones. Best approach is Space Optimized DP with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subarrays	O(n³)	O(1)	Try every possible subarray with every possible deletion
Space Optimized DP	O(n)	O(1)	Optimize space by using variables instead of arrays
Dynamic Programming - Single Pass	O(n)	O(n)	Track maximum sum with 0 and 1 deletions simultaneously

Brute Force - Try All Subarrays — Algorithm Steps

Step 1: Iterate through all possible subarrays
Step 2: For each subarray, try deleting each element
Step 3: Track maximum sum found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Subarrays

Consider every contiguous subarray

Try Each Deletion

For each subarray, try deleting each element

Track Maximum

Keep the highest sum found

Code -

solution.c — C

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

int solution(int* arr, int n) {
    int maxSum = INT_MIN;
    
    // Try all subarrays
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Subarray from i to j
            int currentSum = 0;
            for (int x = i; x <= j; x++) {
                currentSum += arr[x];
            }
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
            
            // Try deleting each element in this subarray
            for (int k = i; k <= j; k++) {
                if (j > i) { // Ensure at least one element remains
                    int deletedSum = currentSum - arr[k];
                    if (deletedSum > maxSum) {
                        maxSum = deletedSum;
                    }
                }
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(arr, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops - start position, end position, and deletion position

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum sum

✓ Linear Space

73.9K Views

Medium Frequency

~25 min Avg. Time

1.8K 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 - Try All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler