Right, that makes sense - but how to determine that minimum/maximum value?
ZenBeam’s restriction is correct. To see this, ask a slightly different question: Given N, A=x[sub]1[/sub], and B=x[sub]N[/sub], what are the maximum sum S and the minimum sum s that I can form, given the maximum allowable consecutive-difference magnitude r>0? (You are interested in the “inverses” of S and s, as r varies for fixed N, A, B: that is, you are given the sum and want to find the minimum required difference magnitude.)
The answer should be obvious. For the maximum sum, we just make every term as large as possible:
x[sub]k[/sub] = min { A+(k-1)r, B+(N-k)r } ;
likewise for the minimum sum we make every term as small as possible:
x[sub]k[/sub] = max { A-(k-1)r, B-(N-k)r, 0 }
(note that there are some values of r which don’t give any consistent solutions). So the optimal solutions–the sequences which give the extremal sums for a given maximum-allowed difference–have points lying along lines with slopes ±r, passing through (1,A) and (N,B) (or along the x axis, if these points become negative).
It’s straightforward to compute this sum for a given r: it’s just a sum of two arithmetic series. The ugly part is that you have to compute the “crossover” point. So to find the maximum sum S(r;N,A,B), for example, you have
x[sub]k[/sub] = A+(k-1)r , 1 <= k <= K
x[sub]k[/sub] = B+(N-k)r , K <= k <= N
for some K (here K is a function of A, B, N, r, which you can write down; K is just the x coordinate of the intersection of the line through (1,A) with slope r and the line through (N,B) with slope -r). The two arithmetic-series sums depend on floor(K), so you end up with an equation for S which is not quite a polynomial equation in r, so it is somewhat ugly to invert this equation analytically to find r explicitly as a function of S.
However, for large N you can approximate the sum by an integral, which is just the area of two trapezoids; this winds up giving you a quadratic equation for r. For small N you can separately consider all possible values of floor(K). Alternately, you can numerically compute the extremal sums as functions of r, and use (e.g.) a binary search to converge on the appropriate value.