Editorial for COCI '14 Contest 5 #1 Funghi
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 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 elements (in our case ). This array contains all the consecutive quadruples we need so the application of the described algorithm gives us the required maximum.
Comments