Functions Again Codeforces Question

help
, ,
1

I am solving Functions Again from Codeforces.

I am unable to solve this question and understand the editorial.

Could anyone explain me in solving this question.

Thank you :slight_smile:

2

First notice that the function given to us is actually asking us to calculate the maximum subarray sum on an array holding the absolute differences between all adjacent elements in the given array, after alternatively placing positive and negative signs.

So first, we convert the given array into an array holding the absolute differences between all adjacent elements. Then we make all even positions negative and calculate the maximum subarray sum. Then we swap the signs and make all even positions positive and all odd positions negative and calculate the maximum subarray sum again.

Let’s look at the first sample:

1, 4, 2, 3, 1

becomes 3, 2, 1, 2

Then the 2 arrays we calculate our maximum subarray sum on are:

3, -2, 1, -2 and -3, 2, -1, 2

Given these arrays, the maximum subarray sum is from the first array with a value of 3.

It’s probably helpful to know that in problems where you have (-1)^i within a summation, you multiply every alternate term with -1

4 Likes
3

I did the same thing before posting this question but that approach did not work.

4

Sorry! It is my mistake, though i know it i could not do it correctly. I have forgot to change the odd positions. I got AC. Thank you :slight_smile:

5
Your Bug 
   for(int i=0;i<n;i++)
        {
            if(!(i%2))
                b[i]=-b[i];
        }

This is incorrect, it doesn’t swap the negative and positive positions, it just makes all elements negative.

(Well, you beat me to it)

1 Like
6

Thank you :slight_smile: