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 previousdp[0]
, indicating the maximum sum ending ati
without deletion. -
dp[1][i]
is assigned with the maximum of three cases: the current array element, the sum ofdp[1][i-1]
and the current array element (i.e., if we have performed the deletion before), anddp[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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.