The algorithm described in the task seems nonsensical at first glance. Therefore, we need to uncover it and make it more sensible; we do this with a series of clever observations.

First, let's notice that, regardless of the value of constant ~R~, after ~N~ rotations the array is restored to its initial state. That means that the second part of the algorithm begins operating on the same array as the first part of the algorithm, except that the signs are changed. However, instead of changing the signs, in the second part of the algorithm, we can reduce the sum (instead of increase) by ~A[index]~. Effectively, the first and second parts of the algorithm operate on identical arrays.

The next step is ignoring the rotation. Instead of imagining an array ~A~ that rotates, we can imagine ~N~ different arrays (calculated by rotating array ~A~) which the first and second parts of the algorithm operate on. On the ~i^\text{th}~ of these arrays (let's call it ~a~), the first and second parts of the algorithm jointly perform the following:

$$\displaystyle sum \mathbin{{+}{=}} a[id1]-a[id2+1]$$

where ~id1~ is the smaller, and ~id2~ is the larger of the two indices ~ID[i]~, ~ID[i+1]~. The upper difference reminds us of the difference of prefix-sums, except that the difference needs to be reversed. By changing the signs of all elements of array ~a~, we get a more familiar relation:

$$\displaystyle sum \mathbin{{+}{=}} a[id2+1]-a[id1]$$

If array ~a~ contains prefix-sums¹ of another array ~b~, then the difference of prefix-sums is the sum of the corresponding interval of array ~b~. More precisely,

$$\displaystyle a[id2+1]-a[id1] = b[id1]+\dots+b[id2]$$

The elements of array ~b~ for which the upper formula holds are calculated using a simple formula ~b[i] = a[i+1]-a[i]~. Notice that array ~b~ has ~N-1~ elements.

In a nutshell: the given algorithm actually adds up intervals in arrays ~b_1, \dots, b_N~ which we can construct. But not just any intervals; the intervals in adjacent arrays are ~[ID[i], ID[i+1]]~ and ~[ID[i+1], ID[i+2]]~ (after we properly orient them, from smaller to larger boundary). These intervals have a common edge (~ID[i+1]~). If we imagine arrays ~b_1, \dots, b_N~ as rows of a matrix, it follows that the algorithm in fact adds up the path in that matrix that goes through the interval from ~ID[1]~ to ~ID[2]~ in the first row, goes down to the second row, in it goes through the interval from ~ID[2]~ to ~ID[3]~, goes down to the third row, in it goes through the interval from ~ID[3]~ to ~ID[4]~ and so on until the ~N^\text{th}~ row, all the while adding up all the elements that it visits in the variable ~sum~.

Therefore, the task comes down to finding the optimal path in a matrix that goes through an interval from left to right or from right to left in each row, goes down to the following row and continues. This is the actual task, all the rest was camouflage.

This task is solved using dynamic programming. The state is a position (row, column) where we are located and the previous step of the path (left, right or down). If the previous step was left, the next step cannot be right and vice-versa. You can work the details out as an exercise.

¹ The ~k^\text{th}~ prefix-sum of array ~b~ is equal to the sum of the first ~K-1~ elements from ~b~.