Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a set of positive integers, not greater than 100000, how can we find the maximal subset such that no three numbers form an Arithmetic progression?

I am looking for some algorithmic approach. If the problem is NP complete, I would like corresponding transformation. Any kind of heuristics will help!

share|improve this question

closed as not constructive by Andrew, Martin, O.L., Daniel Rust, Lord_Farin Jun 15 '13 at 10:51

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

There is a claim from this user that "This problem is from currently going on competition on codechef and should be closed!" –  Zev Chonoles Jun 15 '13 at 9:59

1 Answer 1

Transform the sequence into a sequence of differences:

Eg.: if your original sequence is 1, 3, 8, 7, 7 then the transformed sequence is 2, 5, -1, 0.

Then look for the maximum-length substring that contains no repeating values:

Do a linear-time scan of the sequence to mark the begin and end points of such repeating values as you go along. Then, do a second linear search for the maximum-length subsequence between a pair of end-begin marks that appear in this order without a third mark in between. The algorithm is linear. Its details should be straightforward.

share|improve this answer
how is this algorithms correct? –  user2255279 Jun 15 '13 at 8:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.