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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
