LeetCode 1186: Maximum Subarray Sum with One Deletion Solution

Master LeetCode problem 1186 (Maximum Subarray Sum with One Deletion), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1186. Maximum Subarray Sum with One Deletion

Medium

Array Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming to keep track of the maximum sum with and without deletion at each index of the array. We can then iterate through the array and update the maximum sum accordingly. At each index, we have two choices:

Continue the subarray by adding the current element to the sum.
Start a new subarray with the current element (deleting the previous element or not).

We will maintain two arrays to keep track of these two cases. At each index, we update these arrays and calculate the maximum sum by considering both cases.

Algorithm:

Initialize two arrays dp_keep and dp_delete of size arr.length to keep track of the maximum sum with and without deletion at each index.
Initialize maxSum to the first element of the array.
Iterate through the array from the second element:
- Update dp_keep[i] and dp_delete[i] based on the maximum of the following:
  - dp_keep[i-1] + arr[i] (continuing the subarray)
  - arr[i] (starting a new subarray with the current element)
  - dp_delete[i-1] + arr[i] (starting a new subarray by deleting the previous element)
- Update maxSum by considering the maximum of maxSum, dp_keep[i], and dp_delete[i].
Return maxSum.

Time Complexity:

The time complexity of this solution is O(n) where n is the size of the input array arr.

Space Complexity:

The space complexity of this solution is O(n) as we are using two arrays of size n to store the dynamic programming values.

Solution Code

class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        int[] dp_keep = new int[n];
        int[] dp_delete = new int[n];
        int maxSum = arr[0];
        
        dp_keep[0] = arr[0];
        dp_delete[0] = 0;
        
        for (int i = 1; i < n; i++) {
            dp_keep[i] = Math.max(dp_keep[i-1] + arr[i], arr[i]);
            dp_delete[i] = Math.max(dp_keep[i-1], dp_delete[i-1] + arr[i]);
            maxSum = Math.max(maxSum, Math.max(dp_keep[i], dp_delete[i]));
        }
        
        return maxSum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1186 (Maximum Subarray Sum with One Deletion)?

This page provides optimized solutions for LeetCode problem 1186 (Maximum Subarray Sum with One Deletion) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1186 (Maximum Subarray Sum with One Deletion)?

The time complexity for LeetCode 1186 (Maximum Subarray Sum with One Deletion) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1186 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1186 in Java, C++, or Python.

Back to LeetCode Solutions