Given an array arr[] of N non-zero integers, the task is to find the maximum sum of the array by removing exactly one contiguous set of positive or negative elements.
Examples:
Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: 4
Explanation: Maximum array sum can be obtained by removing subarray arr[0, 1] since arr[0, 1] has same type of elements i.e., negative. Thus, the required sum is 4.Input: arr[] = {2, -10, 4, 2, -8, -7}
Output: -2
Explanation: Maximum array sum can be obtained by removing subarray arr[4, 5] since arr[4, 5] has same type of elements i.e., negative. Thus, the required sum is -2.
Approach: The given problem can be solved based on the following observation i.e to obtain the maximum sum, a contiguous set of negative elements are to be removed since removing positive elements will reduce the array sum. However, if there are no negative elements then remove the smallest element of the array. Follow the steps to solve the problem:
- Traverse the array, arr[] and store the total sum of the array in the variable, say sum.
- Store the maximum contiguous negative sum in a variable, say max_neg.
- If there are no negative elements in the array, then update max_neg to the smallest element of an array.
- Update the value of sum to (sum – max_neg).
- Print the value of sum as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// array after removing either the contiguous// positive or negative elementsvoid maxSum(int arr[], int n){ // Store the total sum of array int sum = 0; // Store the maximum contiguous // negative sum int max_neg = INT_MAX; // Store the sum of current // contiguous negative elements int tempsum = 0; // Store the minimum element of array int small = INT_MAX; // Traverse the array, arr[] for (int i = 0; i < n; i++) { // Update the overall sum sum += arr[i]; // Store minimum element of array small = min(small, arr[i]); // If arr[i] is positive if (arr[i] > 0) { // Update temp_sum to 0 tempsum = 0; } else { // Add arr[i] to temp_sum tempsum += arr[i]; } // Update max_neg max_neg = min(max_neg, tempsum); } // If no negative element in array // then remove smallest positive element if (max_neg == 0) { max_neg = small; } // Print the required sum cout << sum - max_neg;}// Driver Codeint main(){ // Given Input int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call maxSum(arr, n); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to find the maximum sum of// array after removing either the contiguous// positive or negative elementsstatic void maxSum(int arr[], int n){ // Store the total sum of array int sum = 0; // Store the maximum contiguous // negative sum int max_neg = Integer.MAX_VALUE; // Store the sum of current // contiguous negative elements int tempsum = 0; // Store the minimum element of array int small = Integer.MAX_VALUE; // Traverse the array, arr[] for(int i = 0; i < n; i++) { // Update the overall sum sum += arr[i]; // Store minimum element of array small = Math.min(small, arr[i]); // If arr[i] is positive if (arr[i] > 0) { // Update temp_sum to 0 tempsum = 0; } else { // Add arr[i] to temp_sum tempsum += arr[i]; } // Update max_neg max_neg = Math.min(max_neg, tempsum); } // If no negative element in array // then remove smallest positive element if (max_neg == 0) { max_neg = small; } // Print the required sum System.out.println(sum - max_neg);}// Driver Codepublic static void main(String[] args) { // Given Input int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = arr.length; // Function Call maxSum(arr, n);}}// This code is contributed by Dharanendra L V. |
Python3
# python 3 program for the above approachimport sys# Function to find the maximum sum of# array after removing either the contiguous# positive or negative elementsdef maxSum(arr, n): # Store the total sum of array sum = 0 # Store the maximum contiguous # negative sum max_neg = sys.maxsize # Store the sum of current # contiguous negative elements tempsum = 0 # Store the minimum element of array small = sys.maxsize # Traverse the array, arr[] for i in range(n): # Update the overall sum sum += arr[i] # Store minimum element of array small = min(small, arr[i]) # If arr[i] is positive if (arr[i] > 0): # Update temp_sum to 0 tempsum = 0 else: # Add arr[i] to temp_sum tempsum += arr[i] # Update max_neg max_neg = min(max_neg, tempsum) # If no negative element in array # then remove smallest positive element if (max_neg == 0): max_neg = small # Print the required sum print(sum - max_neg)# Driver Codeif __name__ == '__main__': # Given Input arr = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(arr) # Function Call maxSum(arr, n) # This code is contributed by bgangwar59. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum sum of// array after removing either the contiguous// positive or negative elementsfunction maxSum(arr, n) { // Store the total sum of array let sum = 0; // Store the maximum contiguous // negative sum let max_neg = Number.MAX_SAFE_INTEGER; // Store the sum of current // contiguous negative elements let tempsum = 0; // Store the minimum element of array let small = Number.MAX_SAFE_INTEGER; // Traverse the array, arr[] for (let i = 0; i < n; i++) { // Update the overall sum sum += arr[i]; // Store minimum element of array small = Math.min(small, arr[i]); // If arr[i] is positive if (arr[i] > 0) { // Update temp_sum to 0 tempsum = 0; } else { // Add arr[i] to temp_sum tempsum += arr[i]; } // Update max_neg max_neg = Math.min(max_neg, tempsum); } // If no negative element in array // then remove smallest positive element if (max_neg == 0) { max_neg = small; } // Print the required sum document.write(sum - max_neg);}// Driver Code// Given Inputlet arr = [-2, -3, 4, -1, -2, 1, 5, -3];let n = arr.length;// Function CallmaxSum(arr, n);// This code is contributed by gfgking.</script> |
C#
// C# program for the above approachusing System;class GFG{// Function to find the maximum sum of// array after removing either the contiguous// positive or negative elementsstatic void maxSum(int []arr, int n){ // Store the total sum of array int sum = 0; // Store the maximum contiguous // negative sum int max_neg = Int32.MaxValue; // Store the sum of current // contiguous negative elements int tempsum = 0; // Store the minimum element of array int small = Int32.MaxValue; // Traverse the array, arr[] for(int i = 0; i < n; i++) { // Update the overall sum sum += arr[i]; // Store minimum element of array small = Math.Min(small, arr[i]); // If arr[i] is positive if (arr[i] > 0) { // Update temp_sum to 0 tempsum = 0; } else { // Add arr[i] to temp_sum tempsum += arr[i]; } // Update max_neg max_neg = Math.Min(max_neg, tempsum); } // If no negative element in array // then remove smallest positive element if (max_neg == 0) { max_neg = small; } // Print the required sum Console.Write(sum - max_neg);}// Driver Codepublic static void Main(String[] args) { // Given Input int []arr = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = arr.Length; // Function Call maxSum(arr, n);}}// This code is contributed by shivanisinghss2110 |
Output
4
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!
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/maximum-sum-of-array-after-removing-a-positive-or-negative-subarray/ […]
… [Trackback]
[…] Read More Info here to that Topic: geeksforgeeks.org/maximum-sum-of-array-after-removing-a-positive-or-negative-subarray/ […]
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/maximum-sum-of-array-after-removing-a-positive-or-negative-subarray/ […]
… [Trackback]
[…] Here you will find 33612 additional Information on that Topic: geeksforgeeks.org/maximum-sum-of-array-after-removing-a-positive-or-negative-subarray/ […]