Scale Engineer

Maximum Subarray Sum with One Deletion

Med
#1111Time: O(N^2), where N is the length of the array. The nested loops iterate through all possible subarrays, which are O(N^2) in number.Space: O(1), as we only use a few variables to keep track of the current state regardless of the input size.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Two Sigma

Prompt

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.

 

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

 

Constraints:

  • 1 <= arr.length <= 105
  • -104 <= arr[i] <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

A brute-force approach involves examining every possible contiguous subarray, and for each subarray, calculating the maximum possible sum by either keeping all its elements or deleting one of them. To make this slightly more efficient, instead of a naive O(N^3) approach, we can use nested loops to define the start and end of a subarray. While iterating to expand the subarray, we can simultaneously calculate its sum and track its minimum element. This allows us to find the sum with and without a deletion in O(1) time for each expansion step, leading to an overall O(N^2) complexity.

Algorithm

  1. Initialize max_sum to the first element of the array, as the subarray must be non-empty.
  2. Iterate through the array with an outer loop using index i from 0 to n-1. This index i will represent the starting point of a potential subarray.
  3. Inside the outer loop, start an inner loop with index j from i to n-1. This index j will be the ending point of the subarray.
  4. For each subarray arr[i...j], we maintain its current_sum and the min_val within it.
  5. As the inner loop for j progresses, update current_sum by adding arr[j] and min_val by taking min(min_val, arr[j]).
  6. For each subarray arr[i...j], there are two possibilities for the sum: a. No Deletion: The sum is simply current_sum. We update our global max_sum with this value: max_sum = max(max_sum, current_sum). b. One Deletion: We can delete one element. To maximize the sum, we should delete the smallest element, min_val. This is only possible if the subarray has more than one element (i.e., j > i). The sum would be current_sum - min_val. We update our global max_sum with this value as well: max_sum = max(max_sum, current_sum - min_val).
  7. After both loops complete, max_sum will hold the maximum possible subarray sum with at most one deletion.

Walkthrough

This approach iterates through all possible start and end points of a subarray. For each subarray arr[i...j], it calculates two potential maximums: the sum of the subarray as is (no deletion), and the sum of the subarray after removing its smallest element (one deletion). The check j > i ensures that we only consider deletion for subarrays with at least two elements, so they remain non-empty after deletion. The global maximum across all subarrays and both cases (deletion/no deletion) is the answer.

class Solution {    public int maximumSum(int[] arr) {        int n = arr.length;        if (n == 1) {            return arr[0];        }        int maxSum = arr[0];         for (int i = 0; i < n; i++) {            int currentSum = 0;            int minVal = Integer.MAX_VALUE;            for (int j = i; j < n; j++) {                currentSum += arr[j];                minVal = Math.min(minVal, arr[j]);                 // Case 1: No deletion                maxSum = Math.max(maxSum, currentSum);                 // Case 2: One deletion                // We can only delete if the subarray has more than one element                if (j > i) {                    maxSum = Math.max(maxSum, currentSum - minVal);                }            }        }        return maxSum;    }}

Complexity

Time

O(N^2), where N is the length of the array. The nested loops iterate through all possible subarrays, which are O(N^2) in number.

Space

O(1), as we only use a few variables to keep track of the current state regardless of the input size.

Trade-offs

Pros

  • The logic is straightforward and easy to implement.

  • It uses constant extra space.

Cons

  • The O(N^2) time complexity makes it too slow for large input sizes as specified in the constraints, leading to a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int maximumSum(int[] arr) {    int n = arr.length;    int[] left = new int[n];    int[] right = new int[n];    int ans = -(1 << 30);    for (int i = 0, s = 0; i < n; ++i) {      s = Math.max(s, 0) + arr[i];      left[i] = s;      ans = Math.max(ans, left[i]);    }    for (int i = n - 1, s = 0; i >= 0; --i) {      s = Math.max(s, 0) + arr[i];      right[i] = s;    }    for (int i = 1; i < n - 1; ++i) {      ans = Math.max(ans, left[i - 1] + right[i + 1]);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem