MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for my example ({0,1,3,100,102}) and the distance 3 the result could be: {0,3,100} for distance 2 it could be: {0,3,100,102}

Is there an "good" algorithm to do that ?

(This is my first post, sry when i chose the wrong tag)

share|cite|improve this question
You have chosen the wrong forum for this! Try posting it on -- you will get dozens of answers explaining how to solve your problem using dynamic programming. – TonyK Jun 1 '12 at 13:20
isn't this also a mathematical problem ? Something like the Knapsack problem ? – Nick Russler Jun 1 '12 at 13:36
here i got my answer:… – Nick Russler Jun 1 '12 at 15:28
To summarize: The obvious greedy algorithm works. – Douglas Zare Jun 1 '12 at 18:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.