The algorithm can work as follows:
Convert the input to an array where each element has a frequency attribute, discarding duplicate consecutive values in the input to a single node. For example, this input:
1 2 2 4 3 3 3 3
It will be presented as follows:
{val: 1, freq: 1} {val: 2, freq: 2} {val: 4, freq: 1} {val: 3, freq: 4}
Then find local minimum nodes, such as node (3 3 3 3) in 1 (2 2) 4 (3 3 3 3) 4 , that is, nodes with neighbors that have higher values. For those local minima that have an even frequency, “raise” them by applying a step. Repeat this until such local minima exist (with even frequency).
The beginning of the recursive part of the algorithm:
At both ends of the array, work inward to “raise” the values if a higher neighboring neighbor has a higher value. With this rule:
1 2 2 3 5 4 3 3 3 1 1
completely allow. First, from the left side inward:
1 4 5 4 3 3 3 1 1
Then on the right side:
1 4 6 3 2
Please note that if there is an odd frequency (for example, for 3 above) there will be a "remainder" that cannot be increased. The rest of this rule always remains on the outside, therefore, to maximize the potential to the inside of the array.
At this point, the remaining local minima have odd frequencies. Applying a step to such a node will always leave a “remainder” (for example, higher) with the original value. This remaining node can appear anywhere, but it makes sense to consider solutions where this remainder is on the left or right side of the elevator (and not in the middle). For example:
4 1 1 1 1 1 2 3 4
You can enable one of the following:
4 2 2 1 2 3 4
Or:
4 1 2 2 2 3 4
1 in any second or fourth position is the aforementioned “remainder”. Obviously, in this example, the second solution is more promising. In general, the choice is obvious when on one side there is too high a value for merging, since the left largest 4 too high for five values of 1 to get to. 4 looks like a wall.
When the frequency of the local minimum is unity, we can do nothing about it. It actually separates the array on the left and right sides, which do not affect each other. The same is true for the remainder element mentioned above: it splits the array into two parts that do not affect each other.
So, the next step in the algorithm is to search for such minima (when the choice is obvious), apply this step and divide the problem into two different problems that must be solved recursively (above). Therefore, in the last example, the following two problems would be solved separately:
4 2 2 3 4
Then the best of both solutions will be considered a common solution. In this case, it is 5 .
The most difficult part of the algorithm is the consideration of those local minima for which the choice of a place for placing the remainder is not obvious. For instance,
3 3 1 1 1 1 1 2 3
This can go either:
3 3 2 2 1 2 3 3 3 1 2 2 2 3
In this example, the end result is the same for both parameters, but in large arrays it will be less and less obvious. Therefore, both options should be investigated here. In general, you can have many of them, for example 2 in this example:
3 1 1 1 2 3 1 1 1 1 1 3
Each of these two minimums has two options. This is like blowing up too many possibilities for large arrays. But this is not so bad. The algorithm can take opposite options at neighboring lows and thus alternate through the entire array. Thus, preference is given to alternating sections and to receive the maximum possible value in them, while other sections are devoid of value. Now the algorithm turns the tables and switches all the options, so that partitions that were previously approved are now deprived, and vice versa. The solution to both of these alternatives is obtained by recursively solving each section, and then comparing the two “grandiose” solutions to choose the best.
Excerpt
The following is a real-time JavaScript implementation of the above algorithm. Comments are presented which we hope should make them readable.
"use strict"; function Node(val, freq) {
Enter series (space separated):<br> <input id="inp" size="60" value="2 3 1 1 2 2"><button id="go">Solve</button> <br> <input id="len" size="4" value="30"><button id="rand">Produce random series of this size and solve</button> <pre id="out"></pre>
As you can see, the program creates a reduced array with the maximum value included. In general, there can be many massive arrays that have this maximum; only one is provided.