Maximum subarray sum possible after removing at most one subarray

0 0 7 minutes read

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 Code
int 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 Code
int 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 approach
import 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 subarray
def 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 code
arr = [ 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 approach
using System;
 
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
    Console.WriteLine(ans);
}
 
// Driver code
static 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:

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!