Given an array arr[] consisting of N integers, the task is to find the maximum sum of any subarray possible after removing at most one subarray from the given array.
Examples:
Input: arr[] = {-1, 5, 2, -1, 6}
Output: 13
Explanation:
The maximum sum can be obtained by selecting the subarray {5, 2, -1, 6} and removing the subarray {-1}.Input: arr[] = {7, 6, -1, -4, -5, 7, 1, -2, -3}
Output: 21
Approach: Follow the steps to solve the problem:
- Find the index of the left(l) and right(r) most +ve number in the array
- If there are +ve numbers, calculate the sum from index l to r
- else return maximum sub-array sum (calculate using kadane’s algorithm) .
- Now, calculate for the minimum sub-array sum (minSubArrSum) for the range arr[l-r] using kadane’s algorithm
- If minSubArrSum < 0 then the result = sum-minSubArrSum
- else result = sum
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int kadaneMinSubArr(int* nums, int l, int r);int kadaneMaxSubArr(int* nums, int l, int r);void maxSubArrSum(int* nums, int n){ // !T(N) = O(n) // !S(N) = O(1) // finding the left most positive elements and right // most positive elements indexes int l = -1, r = -1, sum = 0, minSubSum; // left most positive element for (int i = 0; i < n; i++) { if (nums[i] >= 0) { l = i; break; } } // right most positive element for (int i = n - 1; i >= 0; i--) { if (nums[i] >= 0) { r = i; break; } } if (l == -1 && r == -1) { // all are -ve numbers // maximum sum of subarray cout << kadaneMaxSubArr(nums, 0, n - 1); return; } // finding sum for (int i = l; i <= r; i++) sum += nums[i]; // minimum sum of subarray minSubSum = kadaneMinSubArr(nums, l, r); cout << ((minSubSum < 0) ? sum - minSubSum : sum);}int kadaneMaxSubArr(int* nums, int l, int r){ // l : left-bound index // r : right-bound index // !T(N) = O(N) // !S(N) = O(1) // finding the maxSubArrSum int sum = nums[l], maxSum = nums[l]; for (int i = l; i <= r; i++) { sum = max(sum + nums[i], nums[i]); maxSum = max(maxSum, sum); } return maxSum;}int kadaneMinSubArr(int* nums, int l, int r){ // !T(N) = O(N) // !S(N) = O(1) // finding the minSubArrSum int sum = nums[l], minSum = nums[l]; for (int i = l; i <= r; i++) { sum = min(sum + nums[i], nums[i]); minSum = min(minSum, sum); } return minSum;}// Driver Codeint main(){ int arr[] = { 7, 6, -1, -4, -5, 7, 1 }; int n = sizeof(arr) / sizeof(arr[0]); maxSubArrSum(arr, n); return 0;}// This code is contributed by jaladisishir96 |
C
// C program for the above approach#include <stdio.h>int kadaneMinSubArr(int* nums, int l, int r);int kadaneMaxSubArr(int* nums, int l, int r);// Find maximum between two numbers.int max(int num1, int num2){ return (num1 > num2) ? num1 : num2;}// Find minimum between two numbers.int min(int num1, int num2){ return (num1 > num2) ? num2 : num1;}void maxSubArrSum(int* nums, int n){ // !T(N) = O(n) // !S(N) = O(1) // finding the left most positive elements and right // most positive elements indexes int l = -1, r = -1, sum = 0, minSubSum; // left most positive element for (int i = 0; i < n; i++) { if (nums[i] >= 0) { l = i; break; } } // right most positive element for (int i = n - 1; i >= 0; i--) { if (nums[i] >= 0) { r = i; break; } } if (l == -1 && r == -1) { // all are -ve numbers // maximum sum of subarray printf("%d", kadaneMaxSubArr(nums, 0, n - 1)); return; } // finding sum for (int i = l; i <= r; i++) sum += nums[i]; // minimum sum of subarray minSubSum = kadaneMinSubArr(nums, l, r); (minSubSum < 0) ? printf("%d", sum - minSubSum) : printf("%d", sum);}int kadaneMaxSubArr(int* nums, int l, int r){ // l : left-bound index // r : right-bound index // !T(N) = O(N) // !S(N) = O(1) // finding the maxSubArrSum int sum = nums[l], maxSum = nums[l]; for (int i = l; i <= r; i++) { sum = max(sum + nums[i], nums[i]); maxSum = max(maxSum, sum); } return maxSum;}int kadaneMinSubArr(int* nums, int l, int r){ // !T(N) = O(N) // !S(N) = O(1) // finding the minSubArrSum int sum = nums[l], minSum = nums[l]; for (int i = l; i <= r; i++) { sum = min(sum + nums[i], nums[i]); minSum = min(minSum, sum); } return minSum;}// Driver Codeint main(){ int arr[] = { 7, 6, -1, -4, -5, 7, 1 }; int n = sizeof(arr) / sizeof(arr[0]); maxSubArrSum(arr, n); return 0;}// This code is contributed by Sania Kumari Gupta |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find maximum // subarray sum possible after // removing at most one subarray public static void maximumSum( int arr[], int n) { long[] preSum = new long[n]; long sum = 0; long maxSum = 0; // Calculate the preSum[] array for (int i = 0; i < n; i++) { // Update the value of sum sum = Math.max(arr[i], sum + arr[i]); // Update the value of maxSum maxSum = Math.max(maxSum, sum); // Update the value of preSum[i] preSum[i] = maxSum; } sum = 0; maxSum = 0; long[] postSum = new long[n + 1]; // Calculate the postSum[] array for (int i = n - 1; i >= 0; i--) { // Update the value of sum sum = Math.max(arr[i], sum + arr[i]); // Update the value of maxSum maxSum = Math.max(maxSum, sum); // Update the value of postSum[i] postSum[i] = maxSum; } // Stores the resultant maximum // sum of subarray long ans = 0; for (int i = 0; i < n; i++) { // Update the value of ans ans = Math.max(ans, preSum[i] + postSum[i + 1]); } // Print the resultant sum System.out.println(ans); } // Driver Code public static void main(String[] args) { int arr[] = { 7, 6, -1, -4, -5, 7, 1 }; maximumSum(arr, arr.length); }} |
Python3
# Python program for the above approach# Function to find maximum# subarray sum possible after# removing at most one subarraydef maximumSum(arr, n) : preSum = [0] * n sum = 0 maxSum = 0 # Calculate the preSum[] array for i in range(n): # Update the value of sum sum = max(arr[i], sum + arr[i]) # Update the value of maxSum maxSum = max(maxSum, sum) # Update the value of preSum[i] preSum[i] = maxSum sum = 0 maxSum = 0 postSum = [0] * (n + 1) # Calculate the postSum[] array for i in range(n-1, -1, -1): # Update the value of sum sum = max(arr[i], sum + arr[i]) # Update the value of maxSum maxSum = max(maxSum, sum) # Update the value of postSum[i] postSum[i] = maxSum # Stores the resultant maximum # sum of subarray ans = 0 for i in range(n): # Update the value of ans ans = max(ans, preSum[i] + postSum[i + 1]) # Print resultant sum print(ans) # Driver codearr = [ 7, 6, -1, -4, -5, 7, 1] N = len(arr)maximumSum(arr, N)# This code is contributed by sanjoy_62. |
C#
// C# program for the above approachusing System;class GFG{// Function to find maximum// subarray sum possible after// removing at most one subarraypublic static void maximumSum(int[] arr, int n){ long[] preSum = new long[n]; long sum = 0; long maxSum = 0; // Calculate the preSum[] array for(int i = 0; i < n; i++) { // Update the value of sum sum = Math.Max(arr[i], sum + arr[i]); // Update the value of maxSum maxSum = Math.Max(maxSum, sum); // Update the value of preSum[i] preSum[i] = maxSum; } sum = 0; maxSum = 0; long[] postSum = new long[n + 1]; // Calculate the postSum[] array for(int i = n - 1; i >= 0; i--) { // Update the value of sum sum = Math.Max(arr[i], sum + arr[i]); // Update the value of maxSum maxSum = Math.Max(maxSum, sum); // Update the value of postSum[i] postSum[i] = maxSum; } // Stores the resultant maximum // sum of subarray long ans = 0; for(int i = 0; i < n; i++) { // Update the value of ans ans = Math.Max(ans, preSum[i] + postSum[i + 1]); } // Print the resultant sum Console.WriteLine(ans);}// Driver codestatic void Main(){ int[] arr = { 7, 6, -1, -4, -5, 7, 1 }; maximumSum(arr, arr.Length);}}// This code is contributed by abhinavjain194 |
Javascript
<script>// Javascript implementation of the above approach // Function to find maximum // subarray sum possible after // removing at most one subarray function maximumSum( arr, n) { let preSum = Array.from({length: n}, (_, i) => 0); let sum = 0; let maxSum = 0; // Calculate the preSum[] array for (let i = 0; i < n; i++) { // Update the value of sum sum = Math.max(arr[i], sum + arr[i]); // Update the value of maxSum maxSum = Math.max(maxSum, sum); // Update the value of preSum[i] preSum[i] = maxSum; } sum = 0; maxSum = 0; let postSum = Array.from({length: n+1}, (_, i) => 0); // Calculate the postSum[] array for (let i = n - 1; i >= 0; i--) { // Update the value of sum sum = Math.max(arr[i], sum + arr[i]); // Update the value of maxSum maxSum = Math.max(maxSum, sum); // Update the value of postSum[i] postSum[i] = maxSum; } // Stores the resultant maximum // sum of subarray let ans = 0; for (let i = 0; i < n; i++) { // Update the value of ans ans = Math.max(ans, preSum[i] + postSum[i + 1]); } // Print the resultant sum document.write(ans); } // Driver Code let arr = [ 7, 6, -1, -4, -5, 7, 1 ]; maximumSum(arr, arr.length);</script> |
21
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Here you will find 63321 more Information on that Topic: geeksforgeeks.org/maximum-subarray-sum-possible-after-removing-at-most-one-subarray/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/maximum-subarray-sum-possible-after-removing-at-most-one-subarray/ […]
… [Trackback]
[…] There you will find 14271 additional Info to that Topic: geeksforgeeks.org/maximum-subarray-sum-possible-after-removing-at-most-one-subarray/ […]