Most Unstable Array

 This is solution of Codeforces question Most Unstable Array

 

This question states that we are given n & m where n = Number of element in array, m = Max sum of array elements. We have to maximise sum of adjacent element & display it.

 

Now coming to base case : 

• If n is 1 then answer will always be 0 because we will not have any adjacent element.
• If n is 2 then answer will always be m because one element will be 0 & the other m. So the resultant will be m.

 Now we will see the rest of case :

 

We will understand it by taking example of third case 5, 5

 We can write solution of the above approach as :

 

2 * 2 + 3 * 2 = 10

 

So we can conclude two things : 

• that for sum to be max adjacent element must be zero 
• & while we will calculate adjacent sum then each element will appear two times.

[0, 2, 0, 3, 0]

 

We can also write this case as :

[0, 0, 5, 0, 0]

 

and answer will simply be 5 * 2 that is m * 2

 

Solution