Leetcode 1186. Maximum Subarray Sum with One Deletion

Problem Description

The problem is asking to find the maximum sum of a subarray from a given array, with the option to delete at most one element in the array.

Subarray here refers to contiguous elements in the array, and it needs to have at least one element after the deletion of one element (if chosen). In other words, we need to find a subarray, delete one element from it (optional), and ensure that the remaining subarray (after deletion) yields the maximum possible sum.

For example, consider an array [1,-2,0,3]. The maximum sum subarray can be obtained by choosing the whole array [1,-2,0,3] and removing -2 from it. Therefore, the subarray [1,0,3] gives us the maximum sum, i.e., 4.

Solution Approach

We solve this problem by applying the Dynamic Programming (DP) technique. Specifically, we maintain two DP states to keep track of the maximum sum subarrays ending at each index i, where the first DP state dp[0][i] records the maximum sum without deletion, and the second dp[1][i] records the maximum sum with at most one deletion.

Initially, both dp[0][0] and dp[1][0] are set to the first element in the array.

For each following array element at index i,

• dp[0][i] is assigned with the maximum of the current array element and the sum of the current array element and previous dp[0], indicating the maximum sum ending at i without deletion.

• dp[1][i] is assigned with the maximum of three cases: the current array element, the sum of dp[1][i-1] and the current array element (i.e., if we have performed the deletion before), and dp[0][i-1] (i.e., delete the current array element). Hence, dp[1][i] maintains the maximum sum with at most one deletion involved.

Finally, among all dp[1][i] (0 <= i < n), the maximum one gives the result.

Python Solution

1
2python
3class Solution:
4    def maximumSum(self, arr: List[int]) -> int:
5        n = len(arr)
6        dp = [[0]*n for _ in range(2)]
7        dp[0][0] = dp[1][0] = arr[0]
8        for i in range(1, n):
9            dp[0][i] = max(arr[i], dp[0][i-1] + arr[i])  # max sum without deletion
10            dp[1][i] = max(arr[i], dp[1][i-1] + arr[i], dp[0][i-1])  # max sum with at most one deletion
11        return max(dp[1])

Java Solution

1
2java
3class Solution {
4    public int maximumSum(int[] arr) {
5        int n = arr.length;
6        int[][] dp = new int[2][n];
7        dp[0][0] = dp[1][0] = arr[0];
8        for (int i = 1; i < n; i++) {
9            dp[0][i] = Math.max(arr[i], dp[0][i-1] + arr[i]);  // max sum without deletion
10            dp[1][i] = Math.max(Math.max(arr[i], dp[1][i-1] + arr[i]), dp[0][i-1]);  // max sum with at most one deletion
11        }
12        int maxSum = dp[1][0];
13        for (int i : dp[1]) maxSum = Math.max(maxSum, i);
14        return maxSum;
15    }
16}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maximumSum(vector<int>& arr) {
6        int n = arr.size();
7        vector<vector<int>> dp(2, vector<int>(n));
8        dp[0][0] = dp[1][0] = arr[0];
9        for (int i = 1; i < n; i++) {
10            dp[0][i] = max(arr[i], dp[0][i-1] + arr[i]);  // max sum without deletion
11            dp[1][i] = max({arr[i], dp[1][i-1] + arr[i], dp[0][i-1]});  // max sum with at most one deletion
12        }
13        return *max_element(dp[1].begin(), dp[1].end());
14    }
15};

C# Solution

1
2csharp
3public class Solution {
4    public int MaximumSum(int[] arr) {
5        int n = arr.Length;
6        int[,] dp = new int[2, n];
7        dp[0, 0] = dp[1, 0] = arr[0];
8        for (int i = 1; i < n; i++) {
9            dp[0, i] = Math.Max(arr[i], dp[0, i-1] + arr[i]);  // max sum without deletion
10            dp[1, i] = Math.Max(arr[i], Math.Max(dp[1, i-1] + arr[i], dp[0, i-1]));  // max sum with at most one deletion
11        }
12        int maxSum = dp[1, 0];
13        for (int i = 0; i < n; i++) maxSum = Math.Max(maxSum, dp[1, i]);
14        return maxSum;
15    }
16}

JavaScript Solution

1
2javascript
3var maximumSum = function(arr) {
4    let n = arr.length; 
5    let dp = Array.from(Array(2), () => Array(n).fill(0));
6    dp[0][0] = dp[1][0] = arr[0];
7    
8    for (let i = 1; i < n; i++){
9        dp[0][i] = Math.max(arr[i], dp[0][i - 1] + arr[i]); // max sum without deletion
10        dp[1][i] = Math.max(arr[i], dp[1][i - 1] + arr[i], dp[0][i - 1]); // max sum with at most one deletion
11    }
12    
13    return Math.max(...dp[1]);
14};

In the JavaScript solution, we follow the same principle where dp[0][i] and dp[1][i] denote the maximum sum of subarray ending at index i without deletion and with at most one deletion respectively. The Math.max function is used to find the maximum of array values.

Conclusion

To summarize, the problem of finding the maximum sum of a subarray with the option to delete at most one element can be efficiently solved using dynamic programming. The key idea is to maintain two states, one for the maximum sum subarray without deletion and the other for the maximum sum subarray with at most one deletion. Then, for each array element, calculate the maximum sum for both states. The solution would be the maximum value of the state with at most one deletion. This approach is applicable in Python, JavaScript, Java, C++, and C#. The time complexity of the solution is O(n), where n is the number of elements in the array.