1186. Maximum Subarray Sum with One Deletion
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 i
th 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:
- Initialize two arrays
left
andright
of sizen
with all zeroes. - Set a temporary sum
s
to 0. - Iterate over the array
arr
while updatingleft
:- For each element
x
, updates
tomax(s, 0) + x
and assignleft[i]
tos
.
- For each element
- Reset
s
to 0 and iterate overarr
in reverse while updatingright
:- For each element
arr[i]
, updates
tomax(s, 0) + arr[i]
and assignright[i]
tos
.
- For each element
- Find the maximum value in
left
, which represents the best case without deletion. - Iterate from the second to the second-last element of the array to check cases with one deletion:
- Update
ans
to the maximum ofans
andleft[i - 1] + right[i + 1]
.
- Update
- 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 EvaluatorExample Walkthrough
Let's use a simple example to demonstrate the solution approach. Consider the array arr = [1, -2, 3, 4, -5, 6]
.
-
Initialize
left
andright
arrays of size6
(the size ofarr
) with all zeroes:left = [0, 0, 0, 0, 0, 0]
,right = [0, 0, 0, 0, 0, 0]
. -
Set
s = 0
. Traversearr
from left to right to fillleft
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 resets = 0
, thenleft[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]
.
-
Reset
s = 0
. Traversearr
from right to left to fillright
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]
.
-
Find the maximum value in
left
, which is8
. -
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 of3
not beneficial)i = 3
:ans = max(9, 3 + 1) = 9
(no change, deletion of4
not beneficial)i = 4
:ans = max(9, 7 + 6) = 13
(deleting-5
)
-
Return
ans
which is now13
, 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 forn
iterations exactly. - The second
for
loop calculates the maximum subarray sums starting at each index (right[]
), iterating backward through the array. It also executesn
iterations. - Computing the maximum value of
left[]
is done inO(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 forn
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[]
andright[]
) are created to store the cumulative sums. - A few variables like
n
,s
,i
,x
, andans
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.
Which of the following uses divide and conquer strategy?
Recommended Readings
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 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 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