1186. Maximum Subarray Sum with One Deletion

MediumArrayDynamic Programming
Leetcode Link

Problem Description

The task is to find the maximum sum of a contiguous subarray from a given array of integers with the option to delete at most one element from the subarray. The subarray must remain non-empty even after a deletion, if any. Thus, the final subarray can either be a contiguous array without deletions or one where a single element has been removed. It's important to optimize the sum even if that means including negative numbers, as long as they maximally contribute to the overall sum.

Intuition

To tackle this problem, we utilize dynamic programming to consider each subarray scenario and the effect of an element deletion. The intuition behind the solution is to calculate, for every index in the array, the maximum subarray sum ending at that index (left) and starting at that index (right). We construct two arrays to keep track of these sums. The left array is filled by traversing the array from left to right, and the right array is filled by traversing from right to left.

By calculating the left maximum sums, we have the maximum subarray sum possible up to every index, without any deletion. The right array provides us the same, but starting at each index and moving to the end. Then, for every index, assuming that index is the deleted element, we can sum the maximum totals from the left and right arrays—essentially the sums just before and just after the deleted element. This way, we consider the maximum sums possible with one deletion for every index.

We also take into account the possibility of no deletion being optimal by keeping the maximum sum found while calculating the left array. Finally, we simply return the largest sum found, which will either include no deletions or one deletion, whichever yields a larger sum.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming to find the maximum sum of a subarray that can optionally have one element deleted. The approach involves constructing two auxiliary arrays: left and right.

The left array is used to store the maximum subarray sum ending at each index when no deletion occurs. We traverse the array from left to right, updating the current sum s by comparing it with 0 - we never want the sum to drop below 0 because a negative sum would decrease the total achievable sum. For each element x in the array at index i, we calculate s = max(s, 0) + x and then store that in left[i].

Following that, we initialize the right array, which stores the maximum subarray sum starting at each index and again with no deletions allowed. The traversal this time is right to left. Similar to the left array calculation, we update s for each element in a reverse manner, i.e., s = max(s, 0) + arr[i].

Now, these two arrays combined give us the maximum subarray sums before and after each index. The candidate solutions for the maximum sum with one deletion at each index i would be the sum of left[i - 1] + right[i + 1], effectively skipping the ith element.

We then compute the maximum value from the left array, which represents the maximum subarray sum without any deletion. Also, we iterate through the array to find the maximum sum if one deletion occurs, using the method described above.

The returned result is the maximum sum found, ans, taking into account both scenarios - with and without a single deletion. This approach ensures that all possible subarrays are accounted for, and the optimal solution is determined accurately.

Here's code execution visualized step by step:

  1. Initialize two arrays left and right of size n with all zeroes.
  2. Set a temporary sum s to 0.
  3. Iterate over the array arr while updating left:
    • For each element x, update s to max(s, 0) + x and assign left[i] to s.
  4. Reset s to 0 and iterate over arr in reverse while updating right:
    • For each element arr[i], update s to max(s, 0) + arr[i] and assign right[i] to s.
  5. Find the maximum value in left, which represents the best case without deletion.
  6. Iterate from the second to the second-last element of the array to check cases with one deletion:
    • Update ans to the maximum of ans and left[i - 1] + right[i + 1].
  7. Return ans which now contains the maximum subarray sum allowing for at most one deletion.

The algorithm has a linear time complexity O(n) due to the single pass made to fill both the left and right arrays.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a simple example to demonstrate the solution approach. Consider the array arr = [1, -2, 3, 4, -5, 6].

  1. Initialize left and right arrays of size 6 (the size of arr) with all zeroes: left = [0, 0, 0, 0, 0, 0], right = [0, 0, 0, 0, 0, 0].

  2. Set s = 0. Traverse arr from left to right to fill left array:

    • i = 0: s = max(0, 0) + 1 = 1, left[0] = 1
    • i = 1: s = max(1, 0) - 2 = -1, but since we can't have negative sums reset s = 0, then left[1] = 0
    • i = 2: s = max(0, 0) + 3 = 3, left[2] = 3
    • i = 3: s = max(3, 0) + 4 = 7, left[3] = 7
    • i = 4: s = max(7, 0) - 5 = 2, left[4] = 2
    • i = 5: s = max(2, 0) + 6 = 8, left[5] = 8 Now, left = [1, 0, 3, 7, 2, 8].

  3. Reset s = 0. Traverse arr from right to left to fill right array:

    • i = 5: s = max(0, 0) + 6 = 6, right[5] = 6
    • i = 4: s = max(6, 0) - 5 = 1, right[4] = 1
    • i = 3: s = max(1, 0) + 4 = 5, right[3] = 5
    • i = 2: s = max(5, 0) + 3 = 8, right[2] = 8
    • i = 1: s = max(8, 0) - 2 = 6, right[1] = 6
    • i = 0: s = max(6, 0) + 1 = 7, right[0] = 7 Now, right = [7, 6, 8, 5, 1, 6].

  4. Find the maximum value in left, which is 8.

  5. Iterate from the second to the second-last element of the array to check cases with one deletion. We need to consider left[i - 1] + right[i + 1]:

    • i = 1: ans = max(0, 1 + 8) = 9 (deleting -2)
    • i = 2: ans = max(9, 1 + 5) = 9 (no change, deletion of 3 not beneficial)
    • i = 3: ans = max(9, 3 + 1) = 9 (no change, deletion of 4 not beneficial)
    • i = 4: ans = max(9, 7 + 6) = 13 (deleting -5)

  6. Return ans which is now 13, the maximum subarray sum if at most one deletion is allowed.

The final result for this example is a sum of 13, which is achieved by the subarray [1, 3, 4, 6] with the deletion of -5. This walkthrough illustrates how the dynamic programming solution accounts for all possible scenarios to find the maximum sum of a contiguous subarray with at most one deletion.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumSum(self, arr: List[int]) -> int:
5        # Calculate the length of the input array
6        n = len(arr)
7      
8        # Initialize two lists to store the maximum subarray sum from left and right
9        max_sum_left = [0] * n
10        max_sum_right = [0] * n
11      
12        # Calculate the maximum subarray sum from the left
13        current_sum = 0
14        for i, value in enumerate(arr):
15            current_sum = max(current_sum, 0) + value
16            max_sum_left[i] = current_sum
17      
18        # Reset the current sum for the next loop
19        current_sum = 0
20      
21        # Calculate the maximum subarray sum from the right
22        for i in range(n - 1, -1, -1):
23            current_sum = max(current_sum, 0) + arr[i]
24            max_sum_right[i] = current_sum
25      
26        # Find the maximum sum of the non-empty subarray
27        max_sum = max(max_sum_left)
28      
29        # Traverse the array and find the maximum sum by potentially removing one element
30        for i in range(1, n - 1):
31            max_sum = max(max_sum, max_sum_left[i - 1] + max_sum_right[i + 1])
32      
33        # Return the maximum sum found
34        return max_sum
35
36# Example usage:
37# sol = Solution()
38# print(sol.maximumSum([1, -2, 0, 3]))  # Output: 4
39
1class Solution {
2    public int maximumSum(int[] arr) {
3        int n = arr.length; // Store the length of the array.
4        int[] leftMaxSum = new int[n]; // Maximum subarray sum ending at each index from the left.
5        int[] rightMaxSum = new int[n]; // Maximum subarray sum starting at each index from the right.
6        int maxSum = Integer.MIN_VALUE; // Initialize maxSum with the smallest possible integer value.
7      
8        // Calculate the maximum subarray sum from the left and find the max subarray sum without deletion.
9        int currentSum = 0; // Initialize a variable to keep track of the current summation.
10        for (int i = 0; i < n; ++i) {
11            currentSum = Math.max(currentSum, 0) + arr[i]; // Calculate the sum while resetting if negative.
12            leftMaxSum[i] = currentSum; // Store the maximum sum up to the current index from the left.
13            maxSum = Math.max(maxSum, leftMaxSum[i]); // Update the maximum subarray sum seen so far.
14        }
15      
16        // Calculate the maximum subarray sum from the right.
17        currentSum = 0; // Reset the currentSum for the right max subarray calculation.
18        for (int i = n - 1; i >= 0; --i) {
19            currentSum = Math.max(currentSum, 0) + arr[i]; // Calculate the sum while resetting if negative.
20            rightMaxSum[i] = currentSum; // Store the maximum sum up to the current index from the right.
21        }
22      
23        // Check the maximum sum by considering deleting one element from the array.
24        for (int i = 1; i < n - 1; ++i) {
25            // Sum of subarrays left to i excluding arr[i] and right to i excluding arr[i] provides a sum
26            // for the array with arr[i] deleted. Update maxSum if this sum is larger.
27            maxSum = Math.max(maxSum, leftMaxSum[i - 1] + rightMaxSum[i + 1]);
28        }
29      
30        return maxSum; // Return the maximum subarray sum with at most one element deletion.
31    }
32}
33
1#include <vector>
2#include <algorithm> // Include algorithm for max_element
3
4using namespace std;
5
6class Solution {
7public:
8    int maximumSum(vector<int>& arr) {
9        int size = arr.size();
10      
11        // Initialize vectors to keep track of maximum subarray sums 
12        // from the left and from the right.
13        vector<int> maxLeft(size);
14        vector<int> maxRight(size);
15      
16        // Calculate maximum subarray sums from the left.
17        for (int i = 0, currentSum = 0; i < size; ++i) {
18            currentSum = max(currentSum, 0) + arr[i];
19            maxLeft[i] = currentSum;
20        }
21      
22        // Calculate maximum subarray sums from the right.
23        for (int i = size - 1, currentSum = 0; i >= 0; --i) {
24            currentSum = max(currentSum, 0) + arr[i];
25            maxRight[i] = currentSum;
26        }
27      
28        // Initialize the answer with the maximum subarray sum that contains no deletion.
29        int answer = *max_element(maxLeft.begin(), maxLeft.end());
30      
31        // Iterate through the array to find the maximum sum obtainable by deleting one element.
32        for (int i = 1; i < size - 1; ++i) {
33            // The maximum sum with one deletion can be found by
34            // adding the maximum subarray sum to the left of the deleted element
35            // and the maximum subarray sum to the right of the deleted element.
36            answer = max(answer, maxLeft[i - 1] + maxRight[i + 1]);
37        }
38      
39        return answer;
40    }
41};
42
1function maximumSum(arr: number[]): number {
2    const arrLength = arr.length; // Number of elements in the array
3    const dpLeft: number[] = new Array(arrLength); // Dynamic programming array storing max sum from the left
4    const dpRight: number[] = new Array(arrLength); // Dynamic programming array storing max sum from the right
5
6    // Calculate maximum subarray sum from the left for each element
7    for (let i = 0, currentSum = 0; i < arrLength; ++i) {
8        currentSum = Math.max(currentSum, 0) + arr[i];
9        dpLeft[i] = currentSum;
10    }
11
12    // Calculate maximum subarray sum from the right for each element
13    for (let i = arrLength - 1, currentSum = 0; i >= 0; --i) {
14        currentSum = Math.max(currentSum, 0) + arr[i];
15        dpRight[i] = currentSum;
16    }
17
18    // Find the maximum subarray sum already calculated from the left side
19    let maxSum = Math.max(...dpLeft);
20    // Check if any sum can be maximized by removing one element
21    for (let i = 1; i < arrLength - 1; ++i) {
22        maxSum = Math.max(maxSum, dpLeft[i - 1] + dpRight[i + 1]);
23    }
24
25    // Return the maximum sum found
26    return maxSum;
27}
28

Time and Space Complexity

Time Complexity

The given Python code has a time complexity of O(n), where n is the length of the input array arr.

Here's the breakdown of the time complexity:

  • The first for loop iterates through the array to compute the maximum subarray sums ending at each index (left[]). This loop runs for n iterations exactly.
  • The second for loop calculates the maximum subarray sums starting at each index (right[]), iterating backward through the array. It also executes n iterations.
  • Computing the maximum value of left[] is done in O(n) time.
  • Another loop runs through the indices from 1 to n - 2 to find the maximum sum obtained by possibly removing one element. This again is a single pass through the array, which accounts for n operations.
  • Each operation within the loops is done in constant time O(1).

Regarding time complexity, we perform a constant amount of work n times, leading to the overall time complexity of O(n).

Space Complexity

The space complexity of the code is O(n) due to the additional space used for the left[] and right[] arrays, each of size n.

Here is the breakdown of the space complexity:

  • Two arrays of size n (left[] and right[]) are created to store the cumulative sums.
  • A few variables like n, s, i, x, and ans are also used which take up constant space.

Since the size of the two arrays scales with the input, the total additional space required by the algorithm is linear with respect to the input size, thus the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More