What is the time complexity of Maximum Subarray Sum with One Deletion?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Maximum Subarray Sum with One Deletion?

This problem uses Array, Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Maximum Subarray Sum with One Deletion?

Insight 1: Dynamic Programming is key. We can keep track of maximum subarray sums ending at each index, with and without a deletion. Insight 2: We need two states for each index: the maximum subarray sum ending at that index with no deletion, and the maximum subarray sum ending at that index with one deletion.

Which companies ask LeetCode 1186. Maximum Subarray Sum with One Deletion in interviews?

This problem is frequently asked at Two Sigma.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Maximum Subarray Sum with One Deletion - LeetCode 1186 Solution

Maximum Subarray Sum with One Deletion - Complete Solution Guide

Maximum Subarray Sum with One Deletion is LeetCode problem 1186, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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

Detailed Explanation

The problem asks us to find the maximum sum of a subarray within a given array of integers, with the option to delete at most one element from the subarray. The chosen subarray must be non-empty after the (optional) deletion. We need to consider all possible subarrays and, for each subarray, consider both the case where we don't delete any element and the case where we delete one element to maximize the sum.

Solution Approach

The solution uses dynamic programming to maintain two states: `no_del` which stores the maximum sum of a subarray ending at the current index without any deletions, and `one_del` which stores the maximum sum of a subarray ending at the current index with at most one deletion. For each index, we update these states and keep track of the overall maximum sum encountered so far. The approach is based on Kadane's Algorithm, but extended to handle the single deletion.

Step-by-Step Algorithm

Step 1: Initialize `no_del` and `max_so_far` to the first element of the array. Initialize `one_del` to negative infinity, since at the start there are no elements to delete from before the second element.
Step 2: Iterate through the array from the second element (index 1) to the end.
Step 3: For each index `i`, update `one_del`. We have two choices: (a) Extend the previous subarray with one deletion by adding the current element `arr[i]`, or (b) Start a new subarray by deleting the current element from a subarray ending at the previous index with no deletion. So, `one_del = max(one_del + arr[i], no_del)`.
Step 4: Update `no_del` using Kadane's algorithm: either extend the previous subarray with no deletion by adding the current element, or start a new subarray from the current element. `no_del = max(no_del + arr[i], arr[i])`.
Step 5: Update `max_so_far` to be the maximum of the current `max_so_far`, `no_del`, and `one_del`. This ensures we keep track of the overall maximum sum we have encountered.
Step 6: Return `max_so_far`.

Key Insights

Insight 1: Dynamic Programming is key. We can keep track of maximum subarray sums ending at each index, with and without a deletion.
Insight 2: We need two states for each index: the maximum subarray sum ending at that index with no deletion, and the maximum subarray sum ending at that index with one deletion.
Insight 3: The 'one deletion' state depends on the previous 'no deletion' state, so it's crucial to update them in the correct order.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming.

Companies

Asked at: Two Sigma.

Maximum Subarray Sum with One Deletion | LeetCode 1186

Medium

Array Dynamic Programming

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        
        // max sum of a subarray ending at the current index with zero deletions
        int no_del = arr[0];
        // max sum of a subarray ending at the current index with one deletion
        int one_del = Integer.MIN_VALUE;
        
        // The overall maximum sum found so far
        int max_so_far = arr[0];

        for (int i = 1; i < n; i++) {
            // To calculate one_del for the current index i, we have two options:
            // 1. Extend a subarray that already had one deletion by adding arr[i].
            //    The sum would be `one_del + arr[i]`.
            // 2. Take a subarray with no deletions ending at i-1 and delete arr[i].
            //    The sum would be `no_del` (from the previous step).
            // We must update `one_del` before `no_del` as it depends on the previous `no_del` state.
            one_del = Math.max(one_del + arr[i], no_del);

            // To calculate no_del, this is the standard Kadane's algorithm:
            // Either extend the previous subarray or start a new one at arr[i].
            no_del = Math.max(no_del + arr[i], arr[i]);
            
            // The overall maximum sum is the maximum of all values computed so far.
            max_so_far = Math.max(max_so_far, Math.max(no_del, one_del));
            
        }
        return max_so_far;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1186: Maximum Subarray Sum with One Deletion - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming

Companies

Two Sigma

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1186

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize `no_del` and `max_so_far` to the first element of the array. Initialize `one_del` to negative infinity, since at the start there are no elements to delete from before the second element.
2
Step 2: Iterate through the array from the second element (index 1) to the end.
3
Step 3: For each index `i`, update `one_del`. We have two choices: (a) Extend the previous subarray with one deletion by adding the current element `arr[i]`, or (b) Start a new subarray by deleting the current element from a subarray ending at the previous index with no deletion. So, `one_del = max(one_del + arr[i], no_del)`.
4
Step 4: Update `no_del` using Kadane's algorithm: either extend the previous subarray with no deletion by adding the current element, or start a new subarray from the current element. `no_del = max(no_del + arr[i], arr[i])`.
5
Step 5: Update `max_so_far` to be the maximum of the current `max_so_far`, `no_del`, and `one_del`. This ensures we keep track of the overall maximum sum we have encountered.
6
Step 6: Return `max_so_far`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the array once (single for loop), performing constant-time operations at each index. Therefore, the time complexity is O(n). The algorithm uses a fixed number of variables (`no_del`, `one_del`, `max_so_far`), regardless of the input size. Therefore, the space complexity is O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Prefix and Suffix Sums with Iteration

Calculate prefix sums from left to right and suffix sums from right to left. Then, iterate through the array, at each index 'i', calculate the maximum subarray sum by considering deleting the element at 'i'. This will be prefixSum[i-1] + suffixSum[i+1]. Update result with the current maximum encountered so far, also remember to update the maximum by Kadane's Algorithm.

Time: O(n)Space: O(n)

Trade-offs: This approach is easier to understand for some, but it uses O(n) space because it creates prefix and suffix sum arrays. This approach is less efficient than O(1) DP solution.

✨

Key Insights

1Insight 1: Dynamic Programming is key. We can keep track of maximum subarray sums ending at each index, with and without a deletion.
2Insight 2: We need two states for each index: the maximum subarray sum ending at that index with no deletion, and the maximum subarray sum ending at that index with one deletion.
3Insight 3: The 'one deletion' state depends on the previous 'no deletion' state, so it's crucial to update them in the correct order.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: Array with all negative numbers. The algorithm correctly handles this by initializing `max_so_far` to the first element and updating it throughout the loop. It correctly finds the largest single element as the result.
Edge case 2: Empty array (though the problem states that the length is between 1 and 10^5). The C solution handles this. Other solutions may require handling this case.
Edge case 3: Array with only one element. The initialization step handles this case correctly, directly returning the element.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not considering the case where the optimal solution doesn't involve any deletion. Failing to update `max_so_far` with `no_del` can lead to incorrect results.

✗Common mistake 2: Incorrectly updating `one_del` and `no_del`. The update order is crucial because `one_del` depends on the previous value of `no_del`.

✗Common mistake 3: Assuming the deleted element has to be in the middle of the subarray. The deleted element can also be at the beginning or end of the chosen subarray. The dynamic programming approach implicitly handles all these possibilities.

✗Common mistake 4: Initializing `one_del` to 0. This is incorrect because the array might have negative values, and the maximum sum with one deletion might be less than 0. It should be initialized to negative infinity (or the equivalent in the given language).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Financial analysis. Identifying the best investment period in a stock's history, allowing for one potential 'bad day' to be ignored.

🏦Real-world scenario 2: Signal processing. Analyzing a noisy signal and removing a single outlier to maximize the signal's strength.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Maximum Subarray Sum with One Deletion"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?