Longest path among subset of given points
This can be solved exactly with dynamic programming. The running time will be $O(n^2m)$.  It finds the exact optimal sequence, not just an approximation.

Let $A[t,u]$ denote the longest path $p_{s_1},\dots,p_{s_t}$ such that $s_t=u$.  In other words, it is the maximum possible value of $\|p_{s_1} - p_{s_2}\|_2 + \dots + \|p_{s_{t-1}} - p_{s_t}\|_2$ such that $1 \le s_1 &lt; \cdots &lt; s_t = u$.

Notice that we have a recursive equation that defines $A[\cdot,\cdot]$.  In particular,

$$A[t,u] = \max \{ A[t-1,v] + \|p_v - p_u\|_2 : 1 \le v &lt; u\}.$$

Thus, we can fill in the values of $A[t,u]$ incrementally, in order of increasing value of $t$.  Each step requires $O(n)$ time, and there are $nm$ entries to fill in, so the total running time is $O(n^2m)$.

In practice the running time might often be something closer to $O(nm)$ if you terminate the search for $v$ early.  In the recurrence above you might often be able to prove that  if $v$ is much smaller than $u$ the maximum can't be achieved, so you could examine at values of $v$ in decreasing order and stop the iteration early once you know there is no improvement possible with a smaller value of $v$.