Given an array arr[] of N integers. The task is to first find the maximum sub-array sum and then remove at most one element from the sub-array. If there are multiple sub-arrays with the maximum sub-array sum then remove at most a single element such that the maximum sum after removal is maximized. The task is to maximize the sum obtained after removal.
Note: You have to first find the maximum sub-array sum and then remove the element from that sub-array if necessary. Also after removal, the sub-array size should at least be 1.
Examples:Â
Â
Input: arr[] = {1, 2, 3, -2, 3}Â
Output: 9Â
The maximum sub-array sum is given by the sub-array {2, 3, -2, 3}Â
Hence, we can remove -2 to further maximize the sub-array sum.Â
Input: arr[] = {-1, -2}Â
Output: -1Â
The maximum sub-array sum is from the sub-array {-1} and no removal is required.Â
Â
Â
Approach: Use Kadane’s algorithm to find the maximum subarray sum. Once the sum has been find, re-apply Kadane’s algorithm to find the maximum sum again with some minor changes. Use two extra variables in the loop, cnt, and mini. The variable cnt counts the number of elements in sub-array and mini stores the minimum value in all the sub-arrays which have same sum as maximum sub-array. If the minimum element thus obtained is less than 0, then only we remove an element from the subarray, or else we donot.Â
Below is the implementation of the above approach:Â
Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
// Function to return the maximum sub-array sumint maxSubArraySum(int a[], int size){Â
    // Initialized    int max_so_far = INT_MIN, max_ending_here = 0;Â
    // Traverse in the array    for (int i = 0; i < size; i++) {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];Â
        // If sub-array sum is more than the previous        if (max_so_far < max_ending_here)            max_so_far = max_ending_here;Â
        // If sum is negative        if (max_ending_here < 0)            max_ending_here = 0;    }    return max_so_far;}Â
// Function that returns the maximum sub-array sum// after removing an element from the same sub-arrayint maximizeSum(int a[], int n){Â Â Â Â int cnt = 0;Â Â Â Â int mini = INT_MAX;Â Â Â Â int minSubarray = INT_MAX;Â
    // Maximum sub-array sum using Kadane's Algorithm    int sum = maxSubArraySum(a, n);Â
    int max_so_far = INT_MIN, max_ending_here = 0;Â
    // Re-apply Kadane's with minor changes    for (int i = 0; i < n; i++) {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];        cnt++;        minSubarray = min(a[i], minSubarray);Â
        // If sub-array sum is greater than the previous        if (sum == max_ending_here) {Â
            // If elements are 0, no removal            if (cnt == 1)                mini = min(mini, 0);Â
            // If elements are more, then store            // the minimum value in the sub-array            // obtained till now            else                mini = min(mini, minSubarray);        }Â
        // If sum is negative        if (max_ending_here < 0) {Â
            // Re-initialize everything            max_ending_here = 0;            cnt = 0;            minSubarray = INT_MAX;        }    }Â
    return sum - mini;}Â
// Driver codeint main(){Â Â Â Â int a[] = { 1, 2, 3, -2, 3 };Â Â Â Â int n = sizeof(a) / sizeof(a[0]);Â Â Â Â cout << maximizeSum(a, n);Â
    return 0;} |
Java
// Java implementation of the approachimport java.io.*;public class GFG{Â Â Â Â Â // Function to return the maximum sub-array sumstatic int maxSubArraySum(int a[], int size){Â
    // Initialized    int max_so_far = Integer.MIN_VALUE,         max_ending_here = 0;Â
    // Traverse in the array    for (int i = 0; i < size; i++)    {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];Â
        // If sub-array sum is more than the previous        if (max_so_far < max_ending_here)            max_so_far = max_ending_here;Â
        // If sum is negative        if (max_ending_here < 0)            max_ending_here = 0;    }    return max_so_far;}Â
// Function that returns the maximum sub-array sum// after removing an element from the same sub-arraystatic int maximizeSum(int a[], int n){Â Â Â Â int cnt = 0;Â Â Â Â int mini = Integer.MAX_VALUE;Â Â Â Â int minSubarray = Integer.MAX_VALUE;Â
    // Maximum sub-array sum     // using Kadane's Algorithm    int sum = maxSubArraySum(a, n);Â
    int max_so_far = Integer.MIN_VALUE,         max_ending_here = 0;Â
    // Re-apply Kadane's with minor changes    for (int i = 0; i < n; i++)    {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];        cnt++;        minSubarray = Math.min(a[i], minSubarray);Â
        // If sub-array sum is greater than the previous        if (sum == max_ending_here)        {Â
            // If elements are 0, no removal            if (cnt == 1)                mini = Math.min(mini, 0);Â
            // If elements are more, then store            // the minimum value in the sub-array            // obtained till now            else                mini = Math.min(mini, minSubarray);        }Â
        // If sum is negative        if (max_ending_here < 0)        {Â
            // Re-initialize everything            max_ending_here = 0;            cnt = 0;            minSubarray = Integer.MAX_VALUE;        }    }Â
    return sum - mini;}Â
// Driver codepublic static void main(String[] args){Â Â Â Â int a[] = { 1, 2, 3, -2, 3 };Â Â Â Â int n = a.length;Â Â Â Â System.out.println(maximizeSum(a, n));}}Â
// This code is contributed by Code_Mech |
Python3
# Python3 implementation of the approach import sys;Â
# Function to return the maximum sub-array sum def maxSubArraySum(a, size) : Â
    # Initialized     max_so_far = -(sys.maxsize - 1);    max_ending_here = 0; Â
    # Traverse in the array     for i in range(size) :Â
        # Increase the sum         max_ending_here = max_ending_here + a[i]; Â
        # If sub-array sum is more than the previous         if (max_so_far < max_ending_here) :            max_so_far = max_ending_here; Â
        # If sum is negative         if (max_ending_here < 0) :            max_ending_here = 0;          return max_so_far; Â
# Function that returns the maximum # sub-array sum after removing an # element from the same sub-array def maximizeSum(a, n) : Â
    cnt = 0;     mini = sys.maxsize;    minSubarray = sys.maxsize; Â
    # Maximum sub-array sum using    # Kadane's Algorithm     sum = maxSubArraySum(a, n); Â
    max_so_far = -(sys.maxsize - 1);    max_ending_here = 0; Â
    # Re-apply Kadane's with minor changes     for i in range(n) :Â
        # Increase the sum         max_ending_here = max_ending_here + a[i];         cnt += 1;         minSubarray = min(a[i], minSubarray); Â
        # If sub-array sum is greater         # than the previous         if (sum == max_ending_here) :Â
            # If elements are 0, no removal             if (cnt == 1) :                mini = min(mini, 0); Â
            # If elements are more, then store             # the minimum value in the sub-array             # obtained till now             else :                mini = min(mini, minSubarray);                  # If sum is negative         if (max_ending_here < 0) :Â
            # Re-initialize everything             max_ending_here = 0;             cnt = 0;             minSubarray = sys.maxsize; Â
    return sum - mini; Â
# Driver code if __name__ == "__main__" : Â
    a = [ 1, 2, 3, -2, 3 ];     n = len(a)         print(maximizeSum(a, n)); Â
# This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;Â
class GFG{Â Â Â Â Â // Function to return the maximum sub-array sumstatic int maxSubArraySum(int []a, int size){Â
    // Initialized    int max_so_far = int.MinValue,         max_ending_here = 0;Â
    // Traverse in the array    for (int i = 0; i < size; i++)    {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];Â
        // If sub-array sum is more than the previous        if (max_so_far < max_ending_here)            max_so_far = max_ending_here;Â
        // If sum is negative        if (max_ending_here < 0)            max_ending_here = 0;    }    return max_so_far;}Â
// Function that returns the maximum sub-array sum// after removing an element from the same sub-arraystatic int maximizeSum(int []a, int n){Â Â Â Â int cnt = 0;Â Â Â Â int mini = int.MaxValue;Â Â Â Â int minSubarray = int.MaxValue;Â
    // Maximum sub-array sum     // using Kadane's Algorithm    int sum = maxSubArraySum(a, n);Â
    int max_so_far = int.MinValue,         max_ending_here = 0;Â
    // Re-apply Kadane's with minor changes    for (int i = 0; i < n; i++)    {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];        cnt++;        minSubarray = Math.Min(a[i], minSubarray);Â
        // If sub-array sum is greater than the previous        if (sum == max_ending_here)        {Â
            // If elements are 0, no removal            if (cnt == 1)                mini = Math.Min(mini, 0);Â
            // If elements are more, then store            // the minimum value in the sub-array            // obtained till now            else                mini = Math.Min(mini, minSubarray);        }Â
        // If sum is negative        if (max_ending_here < 0)        {Â
            // Re-initialize everything            max_ending_here = 0;            cnt = 0;            minSubarray = int.MaxValue;        }    }Â
    return sum - mini;}Â
// Driver codepublic static void Main(String[] args){Â Â Â Â int []a = { 1, 2, 3, -2, 3 };Â Â Â Â int n = a.Length;Â Â Â Â Console.WriteLine(maximizeSum(a, n));}}Â
// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the approachÂ
// Function to return the maximum sub-array sumfunction maxSubArraySum($a, $size){Â
    // Initialized    $max_so_far = PHP_INT_MIN;    $max_ending_here = 0;Â
    // Traverse in the array    for ( $i = 0; $i < $size; $i++)    {Â
        // Increase the sum        $max_ending_here = $max_ending_here + $a[$i];Â
        // If sub-array sum is more than the previous        if ($max_so_far < $max_ending_here)            $max_so_far = $max_ending_here;Â
        // If sum is negative        if ($max_ending_here < 0)            $max_ending_here = 0;    }    return $max_so_far;}Â
// Function that returns the maximum sub-array sum// after removing an element from the same sub-arrayfunction maximizeSum($a, $n){Â Â Â Â $cnt = 0;Â Â Â Â $mini = PHP_INT_MAX;Â Â Â Â $minSubarray = PHP_INT_MAX;Â
    // Maximum sub-array sum using Kadane's Algorithm    $sum = maxSubArraySum($a, $n);Â
    $max_so_far = PHP_INT_MIN;    $max_ending_here = 0;Â
    // Re-apply Kadane's with minor changes    for ($i = 0; $i < $n; $i++)    {Â
        // Increase the sum        $max_ending_here = $max_ending_here + $a[$i];        $cnt++;        $minSubarray = min($a[$i], $minSubarray);Â
        // If sub-array sum is greater than the previous        if ($sum == $max_ending_here)        {Â
            // If elements are 0, no removal            if ($cnt == 1)                $mini = min($mini, 0);Â
            // If elements are more, then store            // the minimum value in the sub-array            // obtained till now            else                $mini = min($mini, $minSubarray);        }Â
        // If sum is negative        if ($max_ending_here < 0)        {Â
            // Re-initialize everything            $max_ending_here = 0;            $cnt = 0;            $minSubarray = PHP_INT_MAX;        }    }    return $sum - $mini;}Â
    // Driver code    $a = array( 1, 2, 3, -2, 3 );    $n = sizeof($a) / sizeof($a[0]);    echo maximizeSum($a, $n);Â
// This code is contributed by Tushil.?> |
Javascript
<script>// Java script implementation of the approachÂ
// Function to return the maximum sub-array sumfunction maxSubArraySum(a,size){Â
    // Initialized    let max_so_far = Number.MIN_VALUE,        max_ending_here = 0;Â
    // Traverse in the array    for (let i = 0; i < size; i++)    {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];Â
        // If sub-array sum is more than the previous        if (max_so_far < max_ending_here)            max_so_far = max_ending_here;Â
        // If sum is negative        if (max_ending_here < 0)            max_ending_here = 0;    }    return max_so_far;}Â
// Function that returns the maximum sub-array sum// after removing an element from the same sub-arrayfunction maximizeSum(a,n){Â Â Â Â let cnt = 0;Â Â Â Â let mini = Number.MAX_VALUE;Â Â Â Â let minSubarray = Number.MAX_VALUE;Â
    // Maximum sub-array sum    // using Kadane's Algorithm    let sum = maxSubArraySum(a, n);Â
    let max_so_far = Number.MIN_VALUE,        max_ending_here = 0;Â
    // Re-apply Kadane's with minor changes    for (let i = 0; i < n; i++)    {Â
        // Increase the sum        max_ending_here = max_ending_here + a[i];        cnt++;        minSubarray = Math.min(a[i], minSubarray);Â
        // If sub-array sum is greater than the previous        if (sum == max_ending_here)        {Â
            // If elements are 0, no removal            if (cnt == 1)                mini = Math.min(mini, 0);Â
            // If elements are more, then store            // the minimum value in the sub-array            // obtained till now            else                mini = Math.min(mini, minSubarray);        }Â
        // If sum is negative        if (max_ending_here < 0)        {Â
            // Re-initialize everything            max_ending_here = 0;            cnt = 0;            minSubarray = Integer.MAX_VALUE;        }    }Â
    return sum - mini;}Â
// Driver codeÂ
    let a = [ 1, 2, 3, -2, 3 ];    let n = a.length;    document.write(maximizeSum(a, n));Â
Â
// This code is contributed by sravan kumar Gottumukkala</script> |
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!
