Breaking an array into blocks

1. To get three blocks, you need to place two separators (in place of commas). These are combinations, which will be C (5,2) = 5! / (2! (5-2)!) = 10 pieces.

2. Go through them all:

    1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5 

3. For each combination, form a set of blocks, for example:

    2,4 => 50,60 | 90,15 | 70,20 ... 3,4 => 50,60,90 | 15 | 70,20 

4. For each combination, you get the difference (by module):

    2,4 => 50,60 | 90,15 | 70,20 => 110-105 , 105-90 => 5,15 

5. You remember the best combination (or several best combinations), checking the sum of differences, it should be minimal.

UPD You can estimate the execution time of one iteration and estimate how many 4.5 billion iterations will be performed (with 100k elements in the array). Within the framework of the Olympiad, of course, there will be no such task, but there are options for parallelizing the process. Combinations can be numbered ( here I wrote about the numbering of combinations , there is also the name of the article where they solve this problem), break the outer loop into several streams ...

With a large number of elements, a complete search will be suboptimal, of course. You can consider an alternative. Split the array into three (initially equal) parts and move the separators in the right directions depending on the amounts. Those. We begin to sort through combinations from 2.4 in different directions, checking the neighborhood:

 2,4 => 1,4 или 2,5 или 2,3 или 3,4 

As a result, we obtain or not a more optimal combination (or several).

Another option is to choose the initial combination: calculate the sum of all elements of the array, divide by three, and in a loop, in order of accumulation, accumulate the sum to the first third, then to the second. We obtain the initial combination, for which also check the neighborhood.

3-5 items remain the same.