Given an array arr[] of N integers, the task is to find the maximum sum of the array that can be obtained by flipping signs of any subarray of the given array at most once.
Examples:
Input: arr[] = {-2, 3, -1, -4, -2}
Output: 8
Explanation:
Flipping the signs of subarray {-1, -4, -2} modifies the array to {-2, 3, 1, 4, 2}. Therefore, the sum of the array = -2 + 3 + 1 + 4 + 2 = 8, which is the maximum possible.Input: arr[] = {1, 2, -10, 2, -20}
Output: 31
Explanation:
Flipping the signs of subarray {-10, 2, -20} modifies the array to {1, 2, 10, -2, 20}. Therefore, the sum of the array = 1 + 2 + 10 – 2 + 20 = 31, which is the maximum possible.
Naive Approach: The simplest approach is to calculate the total sum of the array and then generate all possible subarrays. Now, for each subarray {A[i], … A[j]}, subtract its sum, sum(A[i], …, A[j]), from the total sum and flip the signs of the subarray elements. After flipping the subarray, add the sum of the flipped subarray, i.e. (-1 * sum(A[i], …, A[j])), to the total sum. Below are the steps:
- Find the total sum of the original array (say total_sum) and store it.
- Now, for all possible subarrays find the maximum of total_sum – 2 * sum(i, j).
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// after flipping a subarrayint maxSumFlip(int a[], int n){ // Stores the total sum of array int total_sum = 0; for (int i = 0; i < n; i++) total_sum += a[i]; // Initialize the maximum sum int max_sum = INT_MIN; // Iterate over all possible subarrays for (int i = 0; i < n; i++) { // Initialize sum of the subarray // before flipping sign int sum = 0; for (int j = i; j < n; j++) { // Calculate the sum of // original subarray sum += a[j]; // Subtract the original // subarray sum and add // the flipped subarray // sum to the total sum max_sum = max(max_sum, total_sum - 2 * sum); } } // Return the max_sum return max(max_sum, total_sum);}// Driver Codeint main(){ int arr[] = { -2, 3, -1, -4, -2 }; int N = sizeof(arr) / sizeof(int); cout << maxSumFlip(arr, N);}// This code is contributed by sanjoy_62 |
Java
// Java program for the above approachimport java.io.*;public class GFG { // Function to find the maximum sum // after flipping a subarray public static int maxSumFlip(int a[], int n) { // Stores the total sum of array int total_sum = 0; for (int i = 0; i < n; i++) total_sum += a[i]; // Initialize the maximum sum int max_sum = Integer.MIN_VALUE; // Iterate over all possible subarrays for (int i = 0; i < n; i++) { // Initialize sum of the subarray // before flipping sign int sum = 0; for (int j = i; j < n; j++) { // Calculate the sum of // original subarray sum += a[j]; // Subtract the original // subarray sum and add // the flipped subarray // sum to the total sum max_sum = Math.max(max_sum, total_sum - 2 * sum); } } // Return the max_sum return Math.max(max_sum, total_sum); } // Driver Code public static void main(String args[]) { int arr[] = { -2, 3, -1, -4, -2 }; int N = arr.length; // Function call System.out.println(maxSumFlip(arr, N)); }} |
Python3
# Python3 program for the above approachimport sys# Function to find the maximum sum# after flipping a subarraydef maxSumFlip(a, n): # Stores the total sum of array total_sum = 0 for i in range(n): total_sum += a[i] # Initialize the maximum sum max_sum = -sys.maxsize - 1 # Iterate over all possible subarrays for i in range(n): # Initialize sum of the subarray # before flipping sign sum = 0 for j in range(i, n): # Calculate the sum of # original subarray sum += a[j] # Subtract the original # subarray sum and add # the flipped subarray # sum to the total sum max_sum = max(max_sum, total_sum - 2 * sum) # Return the max_sum return max(max_sum, total_sum)# Driver Codearr = [-2, 3, -1, -4, -2]N = len(arr)print(maxSumFlip(arr, N))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG { // Function to find the maximum sum // after flipping a subarray public static int maxSumFlip(int[] a, int n) { // Stores the total sum of array int total_sum = 0; for (int i = 0; i < n; i++) total_sum += a[i]; // Initialize the maximum sum int max_sum = int.MinValue; // Iterate over all possible subarrays for (int i = 0; i < n; i++) { // Initialize sum of the subarray // before flipping sign int sum = 0; for (int j = i; j < n; j++) { // Calculate the sum of // original subarray sum += a[j]; // Subtract the original // subarray sum and add // the flipped subarray // sum to the total sum max_sum = Math.Max(max_sum, total_sum - 2 * sum); } } // Return the max_sum return Math.Max(max_sum, total_sum); } // Driver Code public static void Main(String[] args) { int[] arr = { -2, 3, -1, -4, -2 }; int N = arr.Length; // Function call Console.WriteLine(maxSumFlip(arr, N)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approach // Function to find the maximum sum // after flipping a subarray function maxSumFlip(a, n) { // Find the total sum of array let total_sum = 0; for (let i = 0; i < n; i++) total_sum += a[i]; // Using Kadane's Algorithm let max_ending_here = -a[0] - a[0]; let curr_sum = -a[0] - a[0]; for (let i = 1; i < n; i++) { // Either extend previous // sub_array or start // new subarray curr_sum = Math.max(curr_sum + (-a[i] - a[i]), (-a[i] - a[i])); // Keep track of max_sum array max_ending_here = Math.max(max_ending_here, curr_sum); } // Add the sum to the total_sum let max_sum = total_sum + max_ending_here; // Check max_sum was maximum // with flip or without flip max_sum = Math.max(max_sum, total_sum); // Return max_sum return max_sum; } // Driver Code let arr = [ -2, 3, -1, -4, -2 ]; let N = arr.length; // Function Call document.write(maxSumFlip(arr, N)); </script> |
Output
8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: From the above approach, it can be observed that, to obtain maximum array sum, (2 * subarray sum) needs to be maximized for all subarrays. This can be done by using Dynamic Programming. Below are the steps:
- Find the minimum sum subarray from l[] using Kadane’s Algorithm
- This maximizes the contribution of (2 * sum) over all subarrays.
- Add the maximum contribution to the total sum of the array.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum// after flipping a subarrayint maxSumFlip(int a[], int n){ // Stores the total sum of array int total_sum = 0; for (int i = 0; i < n; i++) total_sum += a[i]; // Kadane's algorithm to find the minimum subarray sum int b=0,temp=2e9; for (int i = 0; i < n; i++) { b+=a[i]; if(temp>b) temp=b; if(b>0) b=0; } // Return the max_sum return max(total_sum,total_sum-2*temp);}// Driver Codeint main(){ int arr[] = { -2, 3, -1, -4, -2 }; int N = sizeof(arr) / sizeof(int); cout << maxSumFlip(arr, N);} |
Java
import java.util.*;import java.io.*;// Java program for the above approachclass GFG{ // Function to find the maximum sum // after flipping a subarray static int maxSumFlip(int ar[], int n) { // Stores the total sum of array int total_sum = 0; for (int i = 0 ; i < n ; i++){ total_sum += ar[i]; } // Kadane's algorithm to find the minimum subarray sum int b = 0; int a = 2000000000; for (int i = 0 ; i < n ; i++) { b += ar[i]; if(a > b){ a = b; } if(b > 0){ b = 0; } } // Return the max_sum return Math.max(total_sum, total_sum - 2*a); } // Driver Code public static void main(String args[]) { int arr[] = new int[]{ -2, 3, -1, -4, -2 }; int N = arr.length; System.out.println(maxSumFlip(arr, N)); }}// This code is contributed by entertain2022. |
Python3
def maxsum(l,n): total_sum=sum(l) #kadane's algorithm to find the minimum subarray sum current_sum=0 minimum_sum=0 for i in l: current_sum+=i minimum_sum=min(minimum_sum,current_sum) current_sum=min(current_sum,0) return max(total_sum,total_sum-2*minimum_sum)l=[-2,3,-1,-4,-2]n=len(l)print(maxsum(l,n)) |
C#
// Include namespace systemusing System;// C# program for the above approachpublic class GFG{ // Function to find the maximum sum // after flipping a subarray public static int maxSumFlip(int[] ar, int n) { // Stores the total sum of array var total_sum = 0; for (int i = 0; i < n; i++) { total_sum += ar[i]; } // Kadane's algorithm to find the minimum subarray sum var b = 0; var a = 2000000000; for (int i = 0; i < n; i++) { b += ar[i]; if (a > b) { a = b; } if (b > 0) { b = 0; } } // Return the max_sum return Math.Max(total_sum,total_sum - 2 * a); } // Driver Code public static void Main(String[] args) { int[] arr = new int[]{-2, 3, -1, -4, -2}; var N = arr.Length; Console.WriteLine(GFG.maxSumFlip(arr, N)); }}// This code is contributed by sourabhdalal0001. |
Javascript
<script>function maxsum(l,n){let total_sum = 0;for (let i = 0; i < n; i++) total_sum += l[i]; // kadane's algorithm to find the minimum subarray sumlet current_sum=0let minimum_sum=0for(let i of l){ current_sum += i minimum_sum = Math.min(minimum_sum,current_sum) current_sum = Math.min(current_sum,0)}return Math.max(total_sum, total_sum-2*minimum_sum)}// driver codelet l = [-2, 3, -1, -4, -2]let n = l.lengthdocument.write(maxsum(l,n))// This code is contributed by shinjanpatra</script> |
Output
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Note: Can also be done by finding minimum subarray sum and print max(TotalSum, TotalSum-2*(minsubarraysum))
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!
