Editorial for Another Contest 9 Problem 2 - Counting Down the Days
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
We will assume without loss of generality that the sequence has no values which are equal to zero and has length greater than or equal to 2, as sequences of length 1 are trivial to handle. If the product of all the values is positive, then it is clearly maximal. Otherwise, we can show that it is optimal to remove either the shortest prefix with a negative product or the shortest suffix with a negative product.
Comments