Here is a partial description of a cubic time algorithm in quadratic space. The idea is to determine optimal values for cost(I,j), which is the cost incurred by amalgamating the members from position i increasing (say clockwise around the circle) to position j. Since the sum of entries of this subset is useful, we will keep track of that as well.

We initialize by setting cost(j,j) to zero and sum(j,j) to A[j] as j goes from 1 to N. We assume code to handle indices so that when we add k to an index j, it behaves as usual except that if j+k is greater than N, we convert that to index value (j+k - N).

We are going to start k at 1 and compute cost (j,j+k ) and sum(j,j+k). As k gets larger than 1, it makes sense to find an optimal index m to use to aid in computing the cost, but we will not keep track of that information for this implementation. Now to the loop body, executed once for each k and each j:

m=1
sum(j,j+k)=sum(j,j+m-1) + sum(j+m,j+k)
T=cost(j,j+m-1)+cost(j+m,j+k)
#tmove = m
For m=2 to k step 1 do
   V= cost(j,j+m-1)+cost(j+m,j+k)
   If (V < T)
       T=V
       # tmove=m
Cost(j,k)=T + sum(j,k)
#move(j,k)=tmove

This loop body takes constant space and time at most N inner loop iterations. Since the cost of an interval incorporates the sum of the interval, this computes a minimal cost by finding a series of optimal divisions for each smaller interval. Once k has reached N-1, one can do a comparison of all final costs to find the optimum.

Gerhard "Not Quite The Dynamic Programmer" Paseman, 2019.07.27.

Here is a partial description of a cubic time algorithm in quadratic space. The idea is to determine optimal values for cost(Ij,k) which is the cost incurred by amalgamating the members from position j increasing (say clockwise around the circle) to position m. Since the sum of entries of this subset is useful, we will keep track of that as well.

We initialize by setting cost(j,j) to zero and sum(j,j) to A[j] as j goes from 1 to N. We assume code to handle indices so that when we add k to an index j, it behaves as usual except that if j+k is greater than N, we convert that to index value (j+k - N).

We are going to start k at 1 and compute cost (j,j+k ) and sum(j,j+k). As k gets larger than 1, it makes sense to find an optimal index m to use to aid in computing the cost, but we will not keep track of that information for this implementation. Now to the loop body, executed once for each k and each j:

m=1
sum(j,j+k)=sum(j,j+m-1) + sum(j+m,j+k)
T=cost(j,j+m-1)+cost(j+m,j+k)
#tmove = m
For m=2 to k step 1 do
   V= cost(j,j+m-1)+cost(j+m,j+k)
   If (V < T)
       T=V
       # tmove=m
cost(j,k)=T + sum(j,k)
#move(j,k)=tmove

This loop body takes constant space and time at most N inner loop iterations. Since the cost of an interval incorporates the sum of the interval, this computes a minimal cost by finding a series of optimal divisions for each smaller interval. Once k has reached N-1, one can do a comparison of all final costs to find the optimum.

Gerhard "Not Quite The Dynamic Programmer" Paseman, 2019.07.27.

Here is a partial description of a cubic time algorithm in quadratic space. The idea is to determine optimal values for cost(I,j), which is the cost incurred by amalgamating the members from position i increasing (say clockwise around the circle) to position j. Since the sum of entries of this subset is useful, we will keep track of that as well.

We initialize by setting cost(j,j) to zero and sum(j,j) to A[j] as j goes from 1 to N. We assume code to handle indices so that when we add k to an index j, it behaves as usual except that if j+k is greater than N, we convert that to index value (j+k - N).

We are going to start k at 1 and compute cost (j,j+k ) and sum(j,j+k). As k gets larger than 1, it makes sense to find an optimal index m to use to aid in computing the cost, but we will not keep track of that information for this implementation. Now to the loop body, executed once for each k and each j: m=1 sum(j,j+k)=sum(j,j+m-1) + sum(j+m,j+k) T=cost(j,j+m-1)+cost(j+m,j+k) #tmove = m For m=2 to k step 1 do V= cost(j,j+m-1)+cost(j+m,j+k) If (V < T) T=V # tmove=m Cost(j,k)=T + sum(j,k) #move(j,k)=tmove

This loop body takes constant space and time at most N inner loop iterations. Since the cost of an interval incorporates the sum of the interval, this computes a minimal cost by finding a series of optimal divisions for each smaller interval. Once k has reached N-1, one can do a comparison of all final costs to find the optimum.

Gerhard "Not Quite The Dynamic Programmer" Paseman, 2019.07.27.

Here is a partial description of a cubic time algorithm in quadratic space. The idea is to determine optimal values for cost(I,j), which is the cost incurred by amalgamating the members from position i increasing (say clockwise around the circle) to position j. Since the sum of entries of this subset is useful, we will keep track of that as well.

We initialize by setting cost(j,j) to zero and sum(j,j) to A[j] as j goes from 1 to N. We assume code to handle indices so that when we add k to an index j, it behaves as usual except that if j+k is greater than N, we convert that to index value (j+k - N).

We are going to start k at 1 and compute cost (j,j+k ) and sum(j,j+k). As k gets larger than 1, it makes sense to find an optimal index m to use to aid in computing the cost, but we will not keep track of that information for this implementation. Now to the loop body, executed once for each k and each j:

m=1
sum(j,j+k)=sum(j,j+m-1) + sum(j+m,j+k)
T=cost(j,j+m-1)+cost(j+m,j+k)
#tmove = m
For m=2 to k step 1 do
   V= cost(j,j+m-1)+cost(j+m,j+k)
   If (V < T)
       T=V
       # tmove=m
Cost(j,k)=T + sum(j,k)
#move(j,k)=tmove

This loop body takes constant space and time at most N inner loop iterations. Since the cost of an interval incorporates the sum of the interval, this computes a minimal cost by finding a series of optimal divisions for each smaller interval. Once k has reached N-1, one can do a comparison of all final costs to find the optimum.

Gerhard "Not Quite The Dynamic Programmer" Paseman, 2019.07.27.