Given an array arr[], the task is to find the maximum sum subarray when removal of at most one element is allowed.
Examples:
Input: arr[] = {1, 2, 3, -4, 5}
Output: 11
Explanation: We can get maximum sum subarray by removing -4.Input: arr[] = [-2, -3, 4, -1, -2, 1, 5, -3]
Output: 9
Explanation: We can get maximum sum subarray by removing -2 as,
[4, -1, 1, 5] sums up to 9, which is the maximum achievable sum.
Maximum sum subarray removing at most one element using prefix and suffix array:
Below is the idea to solve the problem:
If the element removal condition is not applied, this problem can be solved using Kadane’s algorithm but here one element can be removed also for increasing maximum sum. This condition can be handled using two arrays, prefix and suffix array. These arrays store the current maximum subarray sum from starting to ith index, and from ith index to ending respectively.
Follow the below steps to Implement the idea:
- Initialize two arrays, one for prefix max sum fw[] and another for suffix max sum bw[].
- Run two for loops
- First one to store the maximum current sum from prefix in fw[] and
- The other loop stores the same for suffix in bw[].
- Getting the current maximum and updating it is the same as Kadane’s algorithm.
- Now for one element removal iterate over each index i, calculate the maximum subarray sum after ignoring ith element i.e. fw[i-1] + bw[i+1]
- So loop for all possible index i and choose the maximum among them.
Below is the implementation of the above approach:
C++
// C++ program to get maximum sum subarray removing// at-most one element#include <bits/stdc++.h>using namespace std;// Method returns maximum sum of all subarray where// removing one element is also allowedint maxSumSubarrayRemovingOneEle(int arr[], int n){ // Maximum sum subarrays in forward and backward // directions int fw[n], bw[n]; // Initialize current max and max so far. int cur_max = arr[0], max_so_far = arr[0]; // calculating maximum sum subarrays in forward // direction fw[0] = arr[0]; for (int i = 1; i < n; i++) { cur_max = max(arr[i], cur_max + arr[i]); max_so_far = max(max_so_far, cur_max); // storing current maximum till ith, in // forward array fw[i] = cur_max; } // calculating maximum sum subarrays in backward // direction cur_max = max_so_far = bw[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) { cur_max = max(arr[i], cur_max + arr[i]); max_so_far = max(max_so_far, cur_max); // storing current maximum from ith, in // backward array bw[i] = cur_max; } // Initializing final ans by max_so_far so that, // case when no element is removed to get max sum // subarray is also handled int fans = max_so_far; // choosing maximum ignoring ith element for (int i = 1; i < n - 1; i++) fans = max(fans, max(0, fw[i - 1]) + max(0, bw[i + 1])); // In this condition we are checking when removing the // ith element so checking the max(0,left)+max(0,right), // because maybe left<0 || right<0 so it wont contribute // to the answer if (fans == 0) { // If no positive element in array so return // max_element return *max_element(arr, arr + n); } return fans;}// Driver code to test above methodsint main(){ int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << maxSumSubarrayRemovingOneEle(arr, N); return 0;} |
Java
// Java program to get maximum sum subarray// removing at-most one elementimport java.io.*;class GFG { // Method returns maximum sum of all subarray where // removing one element is also allowed static int maxSumSubarrayRemovingOneEle(int arr[], int n) { // Maximum sum subarrays in forward and // backward directions int fw[] = new int[n]; int bw[] = new int[n]; // Initialize current max and max so far. int cur_max = arr[0], max_so_far = arr[0]; // Calculating maximum sum subarrays in forward // direction fw[0] = arr[0]; for (int i = 1; i < n; i++) { cur_max = Math.max(arr[i], cur_max + arr[i]); max_so_far = Math.max(max_so_far, cur_max); // Storing current maximum till ith, in // forward array fw[i] = cur_max; } // Calculating maximum sum subarrays in backward // direction cur_max = max_so_far = bw[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) { cur_max = Math.max(arr[i], cur_max + arr[i]); max_so_far = Math.max(max_so_far, cur_max); // Storing current maximum from ith, in // backward array bw[i] = cur_max; } // Initializing final ans by max_so_far so that, // case when no element is removed to get max sum // subarray is also handled int fans = max_so_far; // Choosing maximum ignoring ith element for (int i = 1; i < n - 1; i++) fans = Math.max(fans, fw[i - 1] + bw[i + 1]); return fans; } // Driver code public static void main(String arg[]) { int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int N = arr.length; // Function call System.out.print( maxSumSubarrayRemovingOneEle(arr, N)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python program to get maximum sum subarray removing# at-most one element# Method returns maximum sum of all subarray where# removing one element is also alloweddef maxSumSubarrayRemovingOneEle(arr, n): # Maximum sum subarrays in forward and backward # directions fw = [0 for k in range(n)] bw = [0 for k in range(n)] # Initialize current max and max so far. cur_max, max_so_far = arr[0], arr[0] fw[0] = cur_max # Calculating maximum sum subarrays in forward # direction for i in range(1, n): cur_max = max(arr[i], cur_max + arr[i]) max_so_far = max(max_so_far, cur_max) # Storing current maximum till ith, in # forward array fw[i] = cur_max # Calculating maximum sum subarrays in backward # direction cur_max = max_so_far = bw[n-1] = arr[n-1] i = n-2 while i >= 0: cur_max = max(arr[i], cur_max + arr[i]) max_so_far = max(max_so_far, cur_max) # Storing current maximum from ith, in # backward array bw[i] = cur_max i -= 1 # Initializing final ans by max_so_far so that, # case when no element is removed to get max sum # subarray is also handled fans = max_so_far # Choosing maximum ignoring ith element for i in range(1, n-1): fans = max(fans, fw[i - 1] + bw[i + 1]) return fans# Driver codeif __name__ == '__main__': arr = [-2, -3, 4, -1, -2, 1, 5, -3] N = len(arr) # Function call print(maxSumSubarrayRemovingOneEle(arr, N))# Contributed by: Afzal_Saan |
C#
// C# program to get maximum sum subarray// removing at-most one elementusing System;class GFG { // Method returns maximum sum of all subarray where // removing one element is also allowed static int maxSumSubarrayRemovingOneEle(int[] arr, int n) { // Maximum sum subarrays in forward and // backward directions int[] fw = new int[n]; int[] bw = new int[n]; // Initialize current max and max so far. int cur_max = arr[0], max_so_far = arr[0]; // Calculating maximum sum subarrays in forward // direction fw[0] = arr[0]; for (int i = 1; i < n; i++) { cur_max = Math.Max(arr[i], cur_max + arr[i]); max_so_far = Math.Max(max_so_far, cur_max); // Storing current maximum till ith, in // forward array fw[i] = cur_max; } // Calculating maximum sum subarrays in backward // direction cur_max = max_so_far = bw[n - 1] = arr[n - 1]; for (int i = n - 2; i >= 0; i--) { cur_max = Math.Max(arr[i], cur_max + arr[i]); max_so_far = Math.Max(max_so_far, cur_max); // Storing current maximum from ith, in // backward array bw[i] = cur_max; } // Initializing final ans by max_so_far so that, // case when no element is removed to get max sum // subarray is also handled int fans = max_so_far; // Choosing maximum ignoring ith element for (int i = 1; i < n - 1; i++) fans = Math.Max(fans, fw[i - 1] + bw[i + 1]); return fans; } // Driver code public static void Main() { int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 }; int N = arr.Length; // Function call Console.WriteLine( maxSumSubarrayRemovingOneEle(arr, N)); }}// This code is contributed by anuj_67. |
Javascript
<script>// JavaScript program to get maximum sum subarray // removing at-most one element // Method returns maximum sum of all subarray where// removing one element is also allowedfunction maxSumSubarrayRemovingOneEle(arr, n){ // Maximum sum subarrays in forward and // backward directions let fw = []; let bw = []; // Initialize current max and max so far. let cur_max = arr[0], max_so_far = arr[0]; // calculating maximum sum subarrays in forward // direction fw[0] = arr[0]; for(let i = 1; i < n; i++) { cur_max = Math.max(arr[i], cur_max + arr[i]); max_so_far = Math.max(max_so_far, cur_max); // Storing current maximum till ith, // in forward array fw[i] = cur_max; } // Calculating maximum sum subarrays // in backward direction cur_max = max_so_far = bw[n - 1] = arr[n - 1]; for(let i = n - 2; i >= 0; i--) { cur_max = Math.max(arr[i], cur_max + arr[i]); max_so_far = Math.max(max_so_far, cur_max); // Storing current maximum from ith, in // backward array bw[i] = cur_max; } /* Initializing final ans by max_so_far so that, case when no element is removed to get max sum subarray is also handled */ let fans = max_so_far; // Choosing maximum ignoring ith element for(let i = 1; i < n - 1; i++) fans = Math.max(fans, fw[i - 1] + bw[i + 1]); return fans;}// Driver Codelet arr = [ -2, -3, 4, -1, -2, 1, 5, -3 ];let n = arr.length; document.write( maxSumSubarrayRemovingOneEle(arr, n)); </script> |
PHP
<?php// PHP program to get maximum // sum subarray removing// at-most one element// Method returns maximum sum // of all subarray where removing // one element is also allowedfunction maxSumSubarrayRemovingOneEle( $arr, $n){ // Maximum sum subarrays in // forward and backward directions $fw = array(); $bw = array(); // Initialize current // max and max so far. $cur_max = $arr[0]; $max_so_far = $arr[0]; // Calculating maximum sum // subarrays in forward direction $fw[0] = $arr[0]; for ($i = 1; $i < $n; $i++) { $cur_max = max($arr[$i], $cur_max + $arr[$i]); $max_so_far = max($max_so_far, $cur_max); // Storing current maximum till // ith, in forward array $fw[$i] = $cur_max; } // Calculating maximum sum // subarrays in backward direction $cur_max = $max_so_far = $bw[$n - 1] = $arr[$n - 1]; for ( $i = $n - 2; $i >= 0; $i--) { $cur_max = max($arr[$i], $cur_max + $arr[$i]); $max_so_far = max($max_so_far, $cur_max); // Storing current maximum from // ith, in backward array $bw[$i] = $cur_max; } // Initializing final ans by // max_so_far so that, case // when no element is removed // to get max sum subarray is // also handled $fans = $max_so_far; // Choosing maximum // ignoring ith element for ($i = 1; $i < $n - 1; $i++) $fans = max($fans, $fw[$i - 1] + $bw[$i + 1]); return $fans;}// Driver Code$arr = array(-2, -3, 4, -1, -2, 1, 5, -3);$N = count($arr);// Function callecho maxSumSubarrayRemovingOneEle($arr, $N);// This code is contributed by anuj_67.?> |
Output
9
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach using Constant Space and One-pass -:
Follow the below steps to Implement the idea :
curr represents current max sum including arr[i] -- either curr + arr[i] or arr[i] (if arr[i] > curr + arr[i], meaning dp is negative, we just drop curr and start over from arr[i] as there is no point to keep a negative sum)
prev represents current max sum excluding arr[i]
prev can be x + arr[i] since it already excluded one element previously. Or, it can be previous curr, meaning we exclude current element -- arr[i].
res keep track of the maximum sum seen so far
At each ith index check wether to include that index in sum or not.
For each element x in the array, calculate -:
curr = maximum(prev, x + curr)
prev = maximum(x, x + prev)
res = maximum(res, maximum(curr, prev))
return res; // maximum sum of array with one deletion
C++
#include <bits/stdc++.h>using namespace std;// Method returns maximum sum of all subarray where// removing one element is also allowedint maximumSum(int arr[], int n){ int res = INT_MIN, prev = 0, curr = 0; for (int i = 0; i < n; i++) { // Calculate current maximum sum ending at i curr = max(prev, arr[i] + curr); // Calculate maximum sum ending at i with one // element removed prev = max(arr[i], arr[i] + prev); // Update maximum sum so far res = max(res, max(curr, prev)); } return res;}// Driver codeint main(){ int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << maximumSum(arr, n); return 0;} |
Java
// Java program to get maximum sum subarray// removing at-most one elementimport java.io.*;class GFG { // Method returns maximum sum of all subarray where // removing one element is also allowed public static int maximumSum(int[] arr) { int res = Integer.MIN_VALUE, prev = 0, curr = 0; for (int x : arr) { curr = Math.max(prev, x + curr); prev = Math.max(x, x + prev); res = Math.max(res, Math.max(curr, prev)); } return res; } // Driver code public static void main(String arg[]) { int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; // Function call System.out.print( maximumSum(arr)); }}// This code is contributed by vishalkumarsahu04 |
Python3
# Python program to get maximum sum subarray# removing at-most one elementimport sys# Method returns maximum sum of all subarrays where# removing one element is also alloweddef maximumSum(arr): res = -sys.maxsize - 1 prev = 0 curr = 0 for x in arr: curr = max(prev, x + curr) prev = max(x, x + prev) res = max(res, max(curr, prev)) return res# Driver codeif __name__ == '__main__': arr = [-2, -3, 4, -1, -2, 1, 5, -3] # Function call print(maximumSum(arr)) |
C#
// C# Program for the above approachusing System;class GFG{ // Method returns maximum sum of all subarrays where // removing one element is also allowed public static int maximumSum(int[] arr){ int res = int.MinValue; int prev = 0, curr = 0; foreach (int x in arr){ curr = Math.Max(prev, x + curr); prev = Math.Max(x, x + prev); res = Math.Max(res, Math.Max(curr, prev)); } return res; } // Driver code to test above function public static void Main(string[] args){ int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 }; // Function call Console.Write(maximumSum(arr)); }}// THIS CODE IS CONTRIBUTED BY PIYUSH AGARWAL |
Javascript
function maximumSum(arr) { let res = -Infinity, prev = 0, curr = 0; for (let i = 0; i < arr.length; i++) { let x = arr[i]; // calculate the maximum sum subarray // ending at the current index curr = Math.max(prev, x + curr); // calculate the maximum sum subarray // in which the current index is excluded prev = Math.max(x, x + prev); // update the maximum subarray sum so far res = Math.max(res, Math.max(curr, prev)); } return res;}// Driver codeconst arr = [-2, -3, 4, -1, -2, 1, 5, -3];// Function callconsole.log(maximumSum(arr)); |
Output
9
Time Complexity : O(N)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
