An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of $n$ vectors in the $d$-dimensional Euclidean space, find a subset maximizing the length of the sum vector. We propose an algorithm that finds an optimal solution to this problem in time $O(n^{d-1}(d+\log n))$. In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time. Illustr. 2, bibliogr. 14.