Given N elements (both positive and negative). Find the maximum sum, provided that the first operation is to take some prefix of the sequence and multiply all numbers in this prefix by -1. The second operation is to take some suffix and multiply all numbers in it by -1. The chosen prefix and suffix may intersect.
What is the maximum total sum of the sequence that can be obtained by applying the described operations?
Examples:
Input : -1 -2 -3
Output : 6
Explanation: Multiply prefix {-1, -2} with -1.
Multiply suffix {-3} with -1. We get total
sum as 1 + 2 + 3 = 6
Input : -1 10 -5 10 -2
Output : 18
Explanation: Multiply -1 with prefix {-1} and
multiply -1 with suffix {-2}. Elements after
multiplying {1, 10, -5, 10, 2} and sum is
1 + 10 -5 + 10 + 2 = 18.
Input: -4 2 0 5 0
Output: 11
Explanation: Multiply {-4} with -1. Do not
multiply anything in the suffix, so we get
{4, 2, 0, 5, 0} to get sum as 11.
If desired prefix and suffix intersect, then their common part is remaining with the initial sign, and therefore, this case is equivalent to the case when we take the same suffix and prefix, but without their common part.
We traverse from left to right and see if sum or -the sum is more at any step by multiplying -1 to it, and store the maximum of pre_sum and -pre_sum at any index, and continue this process for all elements.
Then we traverse from end to start, and check whose sum is more either the (prefix_sum at that index + negative sum) or the previous maximum that we obtained, if we find at any index the negative sum + prefix sum at that index appears to be more at any step, then we replace the ans to sum*(-1) + pre_sum.
Implementation:
C++
// CPP program to find maximum array sum// with multiplications of a prefix and a // suffix with -1 allowed.#include <iostream>using namespace std; // function to maximize the sum int maximize(int a[], int n){ // stores the pre sum int presum[n]; // to store sum from 0 to i int sum = 0; // stores the maximum sum with // prefix multiplication with -1. int max_sum = 0; // traverse from 0 to n for (int i = 0; i<n ; i++) { // calculate the presum presum[i] = max_sum ; // calculate sum max_sum += a[i]; sum += a[i]; max_sum = max(max_sum, -sum); } // Initialize answer. int ans = max(sum, max_sum); // traverse from back to start int g = 0; for (int i = n-1; i >= 0; --i) { // stores the sum multiplied by (-1) g -= a[i]; // stores the max of ans and // presum + (-1*negative sum); ans = max(ans, g + presum[i]); } // returns answer return ans; }// driver program to test the above functionint main() { int a[] = {-4, 2, 0, 5, 0}; int n = sizeof(a)/sizeof(a[0]); cout << maximize(a, n); return 0;} |
Java
// JAVA program to find maximum array sum// with multiplications of a prefix and a // suffix with -1 allowed.import java.math.*;class GFG { // function to maximize the sum static int maximize(int a[], int n) { // stores the pre sum int presum[] =new int[n]; // to store sum from 0 to i int sum = 0; // stores the maximum sum with // prefix multiplication with -1. int max_sum = 0; // traverse from 0 to n for (int i = 0; i<n ; i++) { // calculate the presum presum[i] = max_sum ; // calculate sum max_sum += a[i]; sum += a[i]; max_sum = Math.max(max_sum, -sum); } // Initialize answer. int ans = Math.max(sum, max_sum); // traverse from back to start int g = 0; for (int i = n-1; i >= 0; --i) { // stores the sum multiplied by (-1) g -= a[i]; // stores the max of ans and // presum + (-1*negative sum); ans = Math.max(ans, g + presum[i]); } // returns answer return ans; } // driver program to test the above function public static void main(String args[]) { int a[] = {-4, 2, 0, 5, 0}; int n = a.length; System.out.println(maximize(a, n)); }}/*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 program to find maximum array # sum with multiplications of a prefix # and a suffix with -1 allowed.# function to maximize the sum def maximize(a,n) : # stores the pre sum presum = [0] * n # to store sum from 0 to i sm = 0 # stores the maximum sum with # prefix multiplication with -1. max_sum = 0 # traverse from 0 to n for i in range(0,n) : # calculate the presum presum[i] = max_sum # calculate sum max_sum =max_sum + a[i] sm = sm + a[i] max_sum = max(max_sum, -sm) # Initialize answer. ans = max(sm, max_sum) # traverse from back to start g = 0 for i in range(n-1,-1,-1) : # stores the sum multiplied by (-1) g = g - a[i] # stores the max of ans and # presum + (-1*negative sum); ans = max(ans, g + presum[i]) # returns answer return ans # driver program to test the above functiona = [-4, 2, 0, 5, 0]n = len(a)print(maximize(a, n))#This code is contributed by Nikita Tiwari. |
C#
// C# program to find maximum array sum// with multiplications of a prefix and a // suffix with -1 allowed.using System;class GFG{ // function to maximize the sum static int maximize(int []a, int n) { // stores the pre sum int []presum =new int[n]; // to store sum from 0 to i int sum = 0; // stores the maximum sum with // prefix multiplication with -1. int max_sum = 0; // traverse from 0 to n for (int i = 0; i < n ; i++) { // calculate the presum presum[i] = max_sum ; // calculate sum max_sum += a[i]; sum += a[i]; max_sum = Math.Max(max_sum, -sum); } // Initialize answer. int ans = Math.Max(sum, max_sum); // traverse from back to start int g = 0; for (int i = n - 1; i >= 0; --i) { // stores the sum multiplied by (-1) g -= a[i]; // stores the max of ans and // presum + (-1*negative sum); ans = Math.Max(ans, g + presum[i]); } // returns answer return ans; } // Driver Code public static void Main() { int []a = {-4, 2, 0, 5, 0}; int n = a.Length; Console.WriteLine(maximize(a, n)); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to find maximum array sum// with multiplications of a prefix and a // suffix with -1 allowed.// function to maximize the sum function maximize($a, $n){ // stores the pre sum $presum = array(); // to store sum // from 0 to i $sum = 0; // stores the maximum // sum with prefix // multiplication with -1. $max_sum = 0; // traverse from 0 to n for ($i = 0; $i < $n ; $i++) { // calculate the presum $presum[$i] = $max_sum ; // calculate sum $max_sum += $a[$i]; $sum += $a[$i]; $max_sum = max($max_sum, -$sum); } // Initialize answer. $ans = max($sum, $max_sum); // traverse from // back to start $g = 0; for ($i = $n - 1; $i >= 0; --$i) { // stores the sum // multiplied by (-1) $g -= $a[$i]; // stores the max of ans and // presum + (-1*negative sum); $ans = max($ans, $g + $presum[$i]); } // returns answer return $ans; } // Driver Code $a = array(-4, 2, 0, 5, 0); $n = count($a); echo maximize($a, $n); // This code is contributed by anuj_67.?> |
Javascript
<script>// javascript program to find maximum array sum// with multiplications of a prefix and a // suffix with -1 allowed. // function to maximize the sum function maximize(a , n) { // stores the pre sum var presum = Array(n).fill(0); // to store sum from 0 to i var sum = 0; // stores the maximum sum with // prefix multiplication with -1. var max_sum = 0; // traverse from 0 to n for (i = 0; i < n; i++) { // calculate the presum presum[i] = max_sum; // calculate sum max_sum += a[i]; sum += a[i]; max_sum = Math.max(max_sum, -sum); } // Initialize answer. var ans = Math.max(sum, max_sum); // traverse from back to start var g = 0; for (i = n - 1; i >= 0; --i) { // stores the sum multiplied by (-1) g -= a[i]; // stores the max of ans and // presum + (-1*negative sum); ans = Math.max(ans, g + presum[i]); } // returns answer return ans; } // driver program to test the above function var a = [ -4, 2, 0, 5, 0 ]; var n = a.length; document.write(maximize(a, n));// This code is contributed by todaysgaurav </script> |
Output:
11
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for presum array.
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!
