Subarray of length 2 GeeksforGeeks Problem

Task :- Given an array of N integers (possibly negative), we have to maximize the sum of all subarrays by performing the following operation any number of times (possibly 0) :

  • Select any subarray of length 2 and multiply each element of that subarray by -1.

Brute Force Approach :- We cannot try all possible combinations as we can perform the task any number of times.

Also we cannot go for greedy approach because it does not guarantee an optimised solution. For eg -

N = 7 , A = [ 3, -4 ,10 , -6 , 5, 11, -10 ]

If we try to traverse the subarray and check for each element whether we should apply the task on that index to increase the final answer(sum of all subarrays), the answer may or may not be maximized.

When i=0, A[i]= 3 , A[i+1]=-4, if we perform the task on this subarray it looks like our final value will increase because after the task the values become -3,4 which has a sum greater than 3,-4.

If we keep on doing this we will get following arrays on each iteration :

  • A = [ 3, -4 ,10 , -6 , 5, 11, -10 ]

Perform the task for (3,-4) because (-3,4) increases the sum

  • A = [ 3, 4 ,10 , -6 , 5, 11, -10 ]

Do not perform task on (4,10) because (-4,-10) reduces the sum

  • A = [ 3, 4 ,10 , -6 , 5, 11, -10 ]

Do not perform task on (10,-6) because (-10,6) reduces the sum

  • A = [ 3, -4 ,10 , -6 , 5, 11, -10 ]
    Perform the task for (-6,5) because (6,-5) increases the sum
  • A = [ 3, -4 ,10 , 6 , -5, 11, -10 ]

Do not perform task on (-5,11) because (5,-11) reduces the sum

  • A = [ 3, -4 ,10 , -6 , 5, 11, -10 ]

Do not perform task on (11,-10) because (-11,10) reduces the sum

  • A = [ 3, -4 ,10 , -6 , 5, 11, -10 ]

So the final array is [ 3, -4, 10, -6, 5, 11, -10 ] which does not give the maximum sum of all subarrays.

We can further apply operations to maximize the answer. For eg:

Apply the task on (-4,10) so array becomes

A = [ 3, 4 ,-10 , -6 , 5, 11, -10 ]
Then apply operation on (-10,-6), so array becomes

A = [ 3, 4 ,10 , 6 , 5, 11, -10 ] and so on

So this is why the Greedy approach doesn’t work.

Approach :- We have to maximize the sum of all subarrays. To do that we have to find an optimised way instead of making all the subarrays and then taking the sum of each. We can make some observations that in an array of fixed length N, we can see that each element occurs a different number of times while calculating the sum of all subarrays.

For eg — In array of length 4, let’s say arr=[1,2,3,4]

Different subarrays possible are :

[1], [2], [3], [4]

[1,2], [2,3], [3,4]

[1,2,3], [2,3,4]

[1,2,3,4]

The sub-task is to calculate the sum of all subarrays.

We can see that each element of array occurs multiple times like

1 occurs 4 times (1 -> 4)

2 occurs 6 times (2 -> 6)

3 occurs 6 times (3 -> 6)

4 occurs 4 times (4 -> 4)

This 4,6,6,4 are the factors that we get. If we multiply the array with this factor array we will get the final value of each element that contributes to the sum of all subarrays.

A = [1, 2, 3, 4]

factors = [4, 6, 6, 4]

A*factors = [4, 12, 18, 16]

After multiplying the factors the array sum will give the sum of all subarrays.

Let’s observe some patterns to get this factors array.

The image below shows factors for each element for fixed length ‘N’:

The factors array can be obtained using the following formula:

For derivation of this formula refer this problem:

After getting the factors array,if we multiply it with our original array, the task is reduced to perform the task to maximize the sum of the array.

The key is to note that we can perform the task such that we can invert any two numbers (even if they are not adjacent) and still the remaining elements won’t get affected.

The images below shows that how it can be done for any two elements with no elements in between, 1,2,3,4 elements in between :

Now the conclusion being we can invert (change the sign) any two numbers irrespective of their positions without changing the remaining array.

Since we can convert all the negative numbers to positive but in pairs, there are two conditions that can occur. If the number of negative integers in the array are even or odd.

If the array contains an even number of negative integers, all the elements can be inverted by taking two at a time and hence we will get the maximum sum after the array contains all positive elements.

If the array contains an odd number of negative integers, all the integers can be inverted except one.

For eg: arr = [ 1, -2, -3, -5, 6]

There are 3 negative integers (-2,-3,-5) but at a time we pick any two let’s say we picked (-2,-3) and inverted their sign so the remaining negative integer is (-5). There has to be one negative integer remaining but we can further pick two elements in the array one of them being -5 and second will be the minimum (ignoring -5) of the array which is 1 in this case.

So we then pick (1,-5) and invert their sign to get the final array as:

arr = [-1, 2, 3, 5, 6] which will give the maximum sum = 15.

So if the count of negative integers is even, answer would be sum of array by taking every element as positive

And if the count of negative integers is odd, answer would be (sum of array — 2*minimum element) by taking every element as positive.

We subtract the minimum element twice because one time we included it in the sum of the array when we shouldn’t have picked that element and the second time because it’s value would be negative while adding it in the sum of the remaining array.

For above eg :- sum of arr(with all +ve elements) = 1+2+3+5+6=17

Minimum = 1

Answer = sum — 2*minimum = 17–2*1 = 15

Code:-

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store