pinkPanties's blog

Need help with problem.
By pinkPanties, history, 6 hours ago, In English

You are given an array. You must apply the following operation until only one element remains.

You need to tell what is the maximum element that can remain. The array can have negative elements.

The operation is:

Choose an element, remove it, combine it's adjacent one's into sum.

For example: 1 2 3 4 5 -> I remove 3rd element -> 1 6 5.

If element is remove from corner, it is just removed, for example from above, I can remove 1 and array will become 2 3 4 5.

The length of array can be upto 10 ^ 5.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think, the idea is greedy (probably fails on some test case) that we can always try to remove the element, which makes the combined adjacent sum greatest in the present array. E.g., [1,2,3,4,3,2], here the greatest sum of a[i - 1] + a[i + 1] is 6 which is possible from any of the 2 + 4 or 3 + 3 or 4 + 2. In this case, we can remove the smallest element which causes this sum, i.e. remove 3 and get 2 + 4 or 4 + 2. Let's go with first one. [1,6,3,2], by applying the same concept, we can get [1,8] and then [8] only. The reason i think this as answer because we can always try to add something to the greatest element of the array.

→ Reply
»
3 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

Hint : it can be shown that even indexed numbers and odd indexed numbers never sum up. look at the operations parameter-wise for example at first you have a1, a2, a3, a4, a5, a6 after deleting the third element we reach a1, a2 + a4, a5, a6 and still we have the summation of one or more even indexed numbers in the even indexed positions and vice versa for odd indices. The whole claim can be proved by a simple induction.

Full Solution :

Full solution
→ Reply