Given a set of 2D vectors, find the furthest reachable point
Suppose you knew the direction $\hat{d}$ of a longest vector sum. Then finding a subset of vectors that should be included in the longest-vector sum is trivial:


Include $v$ when the dot product $v \cdot \hat{d} &gt; 0$.
Exclude $v$ when $v \cdot \hat{d} &lt; 0$.
There won't be a $v$ where $v \cdot \hat{d} = 0$, unless $v=0$, because that contradicts $\hat{d}$ pointing towards a longest vector sum.


Now consider what happens if we vary $\hat{d}$ away from the optimal direction to get $d^\prime$. The sum-along-directions stays constant... until we turn so much that one of the dot products $v \cdot d^\prime$ switches sign. That only happens when $d^\prime$ is perpendicular to a $v$.

Since we're working in 2-d, we can think in terms of angles instead of directions. We have a function $f(\theta)$ that adds up all vectors $v$ even-slightly-aligned with the angle $\theta$. And we know this function only changes values when $\theta$ is perpendicular to one of the vectors $v$. And we know there are at most $2n$ such critical angles.

Ah.

Algorithm

Make a list of all the critical angles where $f(\theta)$'s value changes due to $\theta$ being perpendicular to a $v$. Sort the list. Find a maximizing $\theta$ by sampling $f$ at the midpoint between each contiguous pair of critical points (remembering to include the midpoint where the angles wrap around). Use that $\theta$ to recover a best set of vectors.

By adjusting the total as vectors cross in and out of alignment, instead of recomputing it every time, the algorithm will run in time $O(n \log n)$ with the most expensive step being the sorting of the critical points.

Here's some quick and dirty pseudo-code. WARNING: THIS CODE WAS WRITTEN BY HAND WITHOUT BEING RUN OR TESTED. IT WILL CONTAIN BUGS.

import math


def dot(u, v):
    return u[0]*v[0] + u[1]*v[1]


def vec_sum(vecs):
    t = [0, 0]
    for v in vecs:
        t[0] += v[0]
        t[1] += v[1]
    return tuple(t)


def vectors_along(vec_set, angle):
    d = (math.cos(angle), math.sin(angle))
    return [v for v in vec_set if dot(d, v) &gt; 0]


def transitions(vecs):
    # compute (critical-angle, vector, entering-vs-leaving) tuples
    results = [(t % (2*math.pi), v, b)
               for v in vecs
               for (t, b) in [(math.atan2(v[0], -v[1]), True),
                              (math.atan2(-v[0], v[1]), False)]]
    return sorted(results, key=lambda e: e[0])


def longest_subset(vecs):
    best_angle = None
    current_total_vec = None
    best_norm = 0
    for transition, vec, entering in transitions(vecs):
        # TODO: If two transitions are less than 0.00001 apart this fails
        # TODO: In particular, equal/opposite vectors cause equal transitions.
        angle = transition + 0.00001
        if current_total_vec is None:
            current_total_vec = vec_sum(vectors_along(vecs, angle))
        else:
            current_total_vec += vec * (1 if entering else -1)
        current_norm = dot(current_total_vec, current_total_vec)
        if current_norm &gt; best_norm:
            best_norm = current_norm
            best_angle = angle
    return vectors_along(vecs, best_angle)


Higher Dimensions

This idea works quickly in 2d, but in 3d the boundaries that add/remove a vector from the along-direction sets are great circles instead of points. So everything gets more complicated and more expensive there and continues to get more complicated as you go to higher dimensions.