Find $k$ numbers that satisfy a condition from a sorted sequence

Question

Suppose given $T= a_1\leq a_2\leq\dots\leq a_n $ that $a_i$ is real number and given a number $k$. we want to find $k$ triples $x_i\leq y_i\leq z_i\in T$ such that $$\sum_{i=1}^ k (y_i-x_i)^2$$ minimized, also each $a_i$ can belong to at most one triple.

How we can solve above problem in $O(nk)$? I think it's possible to use Dynamic programming but i can't find a recurrence relation for my problem. Above problem belong to my final exam that our TA didn't solve it for us and i want how we can solve it.

Answer 1

Note that to minimize the sum, you can always chose $x_i$ and $y_i$ to be consecutive in $T$. The choice of $z_i$ only obliges you to have enough "big values" after having chosen $x_i$ and $y_i$.

I think you could do some dynamic programming using a function like the following:

For $i = 1$ to $n-1$ and $\ell = 0$ to $k$, define $F(i, \ell)$ as the couple composed of:

• the set $S$ of $\ell$ values among $\{1, 2, …, i\}$ that minimizes $\sum\limits_{j\in S} (a_{j+1}-a_j)^2$;
• the number of values that still need to be chosen among $\{a_{i+1}, …, a_n\}$ for $z_1$, …, $z_i$.

The second point is a bit informal and corresponds to the "big values" still needed after chosing as much as possible among $\{a_1, …, a_i\}$.