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.
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, a6after deleting the third element we reacha1, a2 + a4, a5, a6and 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 :
Sum up all the non-negative numbers with odd indices in
SOand all non-negative numbers with even indices inSE. We claim the answer will bemax(SE, SO). by previous part we can easilly show that tbe answer can never be bigger thanmax(SE, SO). consider the case thatSOequals the maximum of the two. First do the operation on all negative numbers with odd indices, this way we will eliminate all negatvie numbers with odd indices. Then do the operations on all the even indexed numbers. The last number equals the sum of non-negative numbers with odd indices. The case ofSEbeing the maximum can be handled similary.The only edge case is when all the initial numbers are negative. The answer will be the maximum of all numbers and can be reached by repeatedly deleting the leftmost/rightmost element