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

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.

• What are $x_i$, $y_i$ and $z_i$? Are they to be chosen among $a_1, …, a_n$? In this case, what is the link between the $i$ in $a_i$ and the $i$ in $x_i$ (and others)? Finally, is $k$ an input of the problem? Please clarify your post accordingly. Dec 20, 2021 at 21:48
• Yes $k$ is input. Dec 20, 2021 at 21:51

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$$.
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\}$$.