Editorial for COCI '14 Contest 5 #1 Funghi


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.

Initially, let's assume that we aren't given a "circular", but a regular array of N elements.

In such an array, how would we find the largest sum of four consecutive elements? We would choose the position of the quadruple using a for loop and check whether its sum is larger than the maximum sum so far. The position of the quadruple must be such that it stays within the array.

In a "circular" array, we must also take into account the quadruples that exceed the array's boundary and continue from the beginning of the array. In order to elegantly include such quadruples in the above algorithm, it is sufficient to double the given array. In other words, concatenate it to itself, creating an array of 2N elements (in our case 16). This array contains all the consecutive quadruples we need so the application of the described algorithm gives us the required maximum.


Comments

There are no comments at the moment.