For instance, if I have a list
[1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
This algorithm should return [1,2,3,4,5,6,7,8,9,10,11].
To clarify, the longest list should run forwards. I was wondering what is an algorithmically efficient way to do this (preferably not O(n^2))?
Also, I’m open to a solution not in python since the algorithm is what matters.
Thank you.
Advertisement
Answer
Here is a simple one-pass O(n) solution:
s = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11,42] maxrun = -1 rl = {} for x in s: run = rl[x] = rl.get(x-1, 0) + 1 print x-run+1, 'to', x if run > maxrun: maxend, maxrun = x, run print range(maxend-maxrun+1, maxend+1)
The logic may be a little more self-evident if you think in terms of ranges instead of individual variables for the endpoint and run length:
rl = {} best_range = xrange(0) for x in s: run = rl[x] = rl.get(x-1, 0) + 1 r = xrange(x-run+1, x+1) if len(r) > len(best_range): best_range = r print list(best_range)