Maximum subarray sum possible after removing at most one subarray
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> |
Output:
21
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
